Tree Traversal 遍历 (recursion+ite

不同遍历方法的定义

Tree的遍历分为三种，分别是inorder, preorder, postorder

image.png

以上面的Tree为例说明如何得出各种traverse方法的遍历结果：

三种遍历的定义：

inorder：left root right。 4 2 5 1 3 上

preorder: root left right。 1 2 4 5 3 右

Postorder: left right. root 4 5 2 3 1 左

看到上面这个Tree，从root开始在四周用红笔勾勒一圈。对于inorder来说，遍历的顺序就是node出现在笔触上方的顺序；对于preorder来说，遍历的顺序就是node出现在笔触右方的顺序；对于postorder来说，遍历的顺序就是node出现在笔触左边的顺序。

recursion方法

对于recursion来说，代码非常简单，基本就是定义的翻译，因此不做过多阐述，仅附上代码。

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        if(root.left != null) {
            list.addAll(inorderTraversal(root.left));
        }
        list.add(root.val);
        if(root.right != null) {
            list.addAll(inorderTraversal(root.right));
        }
        return list;
        
    }

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
            list.add(root.val);
        if(root.left != null) {
            list.addAll(preorderTraversal(root.left));
        }
        if(root.right != null) {
            list.addAll(preorderTraversal(root.right));
        }
        return list;
        
    }

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        if(root.left != null) {
            list.addAll(postorderTraversal(root.left));
        }
        if(root.right != null) {
            list.addAll(postorderTraversal(root.right));
        }
            list.add(root.val);
        return list;
        
    }

iteration 方法

Inorder

Inorder 遍历是左中右顺序，因此一开始要去找最左边的node。

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if (root==null) return res;

        Stack<TreeNode> stack=new Stack<>();
        TreeNode curr=root;

        while(curr!=null || !stack.isEmpty()){
          // 找到最左下角的node  
          while (curr!=null){
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop();
            // 中
            res.add(curr.val);
            // 右
            curr=curr.right;
        }
        return res;
    }

Preorder

preorder是中左右的顺序，因此每次先add中间的node，但是在push back的时候，因为stack是first in last out的顺序，所以先push back 右边的node，接着才是左边的node，那么在pop的时候，才会先得到左边的node。

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode current = stack.pop();
            list.add(current.val);
            // push right
            if(current.right!=null) {
               stack.push(current.right);
            }
            // push left
            if(current.left!=null) {
              stack.push(current.left);
            }
        }
        return list;
    }

Postorder

postorder的顺序是左右中，在这里的实现中采用的顺序是采用倒过来顺序。依次添加 root right left，但是添加时加在了list的最前面，相当于整个添加完后倒了倒顺序。

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            list.add(0,curr.val);
            if(curr.left!=null) {
              stack.push(curr.left);
            }
            if(curr.right!=null) {
               stack.push(curr.right); 
            }
        }
        return list;
    }

Morris方法

这种方法效率高，但理论相对复杂。我也还没有完全搞懂背后的含义，先把代码附上，坑以后再填上吧。

// morris traversal
// inorder  morris
public List<Integer> inorderTraversal(TreeNode root) {
    TreeNode current = root, pre;
    List<Integer> list = new LinkedList<>();
    while(current != null) {
            if(current.left == null) {
                list.add(current.val);
                current = current.right;
            } else {
                pre = current.left;
                while (pre.right != null && pre.right != current) {
                    pre = pre.right;
                } 
                if(pre.right == null) {
                    pre.right = current;
                    current = current.left;
                } else {
                    pre.right = null;
                    list.add(current.val);
                    current = current.right;
                }
            }
        }
        return list;
    }

// preorder morris
public List<Integer> preorderTraversal(TreeNode root) {
    TreeNode current = root, pre;
    List<Integer> list = new LinkedList<>();
    while(current != null) {
        if(current.left == null) {
            list.add(current.val);
            current = current.right;
        } else {
            pre = current.left;
            while(pre.right != null && pre.right != current) {
                pre = pre.right;
            }
            if(pre.right == null) {
                list.add(current.val);
                pre.right = current;
                current = current.left;
            } else {
                pre.right = null;
                current = current.right;
            }
        }
    }
    return list;
}

// morris postorder
public List<Integer> postorderTraversal(TreeNode root) {
    TreeNode dump = new TreeNode(0);
    dump.left = root;
    TreeNode current = dump, pre;
    while(current != null) {
        if(current.left == null) {
            current = current.right;
        } else {
            pre = current.left;
            while (pre.right != null && pre.right != current) {
                pre = pre.right;
            }
            if(pre.right == null) {
                pre.right = current;
                current = current.left;
            } else {
                
            }
        }
    }
}