1.中序遍歷

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/

1.1遞歸

微信圖片_20191017204657_wps圖片.jpg

class Solution {
    List<Integer> result;
    public List<Integer> inorderTraversal(TreeNode root) {
        result =new ArrayList<>();
        if(root==null) return result;
        getMyFixGroup(root);
        return result;
    }

    private void getMyFixGroup(TreeNode root) {
       //加入左邊
        if (root.left != null) {
            getMyFixGroup( root.left );
        }
      //加入根
        result.add( root.val );
     //加入右邊
        if (root.right != null) {
            getMyFixGroup( root.right );
        }
    }
}

1.2非遞歸

微信圖片_20191017204709.jpg

class Solution {
   public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> wait = new Stack<>();
        boolean isRight = false;
        while(!wait.empty()||root!=null){  //1.當當前節(jié)點或者棧內(nèi)的節(jié)點不為空的時候,循環(huán)繼續(xù)
           if(root!=null){    //2.節(jié)點不為null
               if(!isRight&&root.left!=null){//3節(jié)點的左子樹不為null且不是棧內(nèi)取出的節(jié)點
                   wait.add(root);  //4.根節(jié)點加入棧
                   root = root.left; //5.當前節(jié)點置為根的左節(jié)點
               }else{
                   res.add(root.val);  //6.左節(jié)點為null,則根加入結(jié)果,并置當前節(jié)點為根的右節(jié)點
                   root = root.right;
               }
               isRight = false;  //7.不是從棧內(nèi)取出的標志位
           }else{
               root = wait.pop();  //8.當前的節(jié)點為空,但棧不為空,從棧內(nèi)彈出一個節(jié)點
               isRight = true; //9,棧內(nèi)取出的標志位為true
           }
        }
        return res;

    }
}

剩下的遍歷和中序遍歷類似

2.前序遍歷

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

2.1遞歸

class Solution {
     List<Integer> result;
    public List<Integer> preorderTraversal(TreeNode root) {
        result = new ArrayList<>();
        checkMyNode(root);
        return result;
    }

    private void checkMyNode(TreeNode root) {
        if(root == null)return;
        result.add(root.val);
        checkMyNode(root.left);
        checkMyNode(root.right);
    }
}

2.2非遞歸

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> wait = new Stack<>();
        List<Integer> res = new ArrayList<>();
 //1.當當前節(jié)點或者棧內(nèi)的節(jié)點不為空的時候,循環(huán)繼續(xù)
        while(root!=null||!wait.isEmpty()){
            if(root!=null){
//2.根節(jié)點加入結(jié)果
                res.add(root.val);
//3節(jié)點的右子樹不為null
                if(root.right!=null){
//4.加入待處理節(jié)點
                    wait.add(root.right);
                }
//5.根節(jié)點更新為根的左節(jié)點
                root = root.left;
            }else{
//6.如果當前的節(jié)點為null,從棧節(jié)點返回
                root = wait.pop();
            }
        }
        return res;
    }
}

3.后序遍歷

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

3.1遞歸

class Solution {
    List<Integer> result;
    public List<Integer> postorderTraversal(TreeNode root) {
        result = new ArrayList<>();
        if(root != null) {
            checkMyNode(root);
        }
        return result;
    }

    private void checkMyNode(TreeNode root) {
        if(root == null)return;
        checkMyNode(root.left);
        checkMyNode(root.right);
        result.add(root.val);
    }
}

3.2非遞歸

class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
//1.待處理的節(jié)點
        Stack<TreeNode> wait = new Stack<>();
//2.該節(jié)點左右是否已經(jīng)處理的標志
        Stack<Boolean> flag = new Stack<>();
//3.結(jié)果
        List<Integer> res = new ArrayList<>();
        boolean isDeal = false;
        while(root!=null||!wait.isEmpty()){
            if(root!=null){
                if(!isDeal){
                  //1.當前節(jié)點未處理,且左右節(jié)點的各種情況
                    if(root.left == null&&root.right == null){
                        res.add(root.val);
                        root = null;
                    }else if(root.left==null&&root.right!=null){
                        wait.add(root);
                        flag.add(true);
                        root = root.right;
                    }else if(root.left!=null&&root.right==null){
                        wait.add(root);
                        flag.add(true);
                        root = root.left;
                    }else if(root.left!=null&&root.right!=null){
                        wait.add(root);
                        flag.add(true);
                        wait.add(root.right);
                        flag.add(false);
                        root = root.left;
                    }
                    isDeal = false;
                }else{
//當前節(jié)點的左右節(jié)點都已經(jīng)處理過了,直接接入結(jié)果
                    res.add(root.val);
                    if(!wait.empty()){
                        root = wait.pop();
                        isDeal = flag.pop();
                    }else{
                        root = null;
                    }
                }
            }else{
//從待處理的棧中彈出結(jié)果
                root = wait.pop();
                isDeal = flag.pop();
            }
        }
        return res;

    }
}