Tree Traversal总结

Depth-first:pre-order, in-order, post-order

Pre-order:
preorder(node)
    if node == null then return
    visit(node)
    preorder(node.left)
    preorder(node.right)

1. public List<Integer> preorder(TreeNode root){
   
2.     List<Integer> res = new      LinkedList<Integer>();
   
3.     if(root==null) return res;
   
4.     res.add(root.val);
   
5.     res.addAll(preorder(root.left));
   
6.     res.addAll(preorder(root.right));
   
7.     return res;
   
8. }

复制代码

iterativePreorder(node)
    parentStack = empty stack
    while (node parentStack.isEmpty() or node != null)
        if(node != null)
            visit(node)
            if (node.right != null) parentStack.push(node.right)
            node = node.left
        else
            node = parentStack.pop()

1. public List<Integer>  iterativePreorder(TreeNode root){
   
2.     List<Integer> res = new LinkedList<Integer>();
   
3.     if(root==null) return res;
   
4.     Stack<TreeNode> stack = new Stack<TreeNode>();
   
5.     Stack.push(root);
   
6.     while(!stack.isEmpty()){
   
7.         TreeNode top = stack.pop();
   
8.         res.add(top.val);
   
9.         if(root.right!=null) stack.push(top.right);
   
10.         if(root.left!=null) stack.push(top.left);
    
11.     }
    
12.     return res;
    
13. }

复制代码

LeetCode Link: https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

In-order：
inorder(node)
    if node == null then return
    inorder(node.left)
    visit(node)
    inorder(node.right)

1. List<Integer> inorder(TreeNode root){
   
2.     List<Integer> res = new LinkedList<Integer>();
   
3.     if(root==null) return res;
   
4.     res.addAll(inorder(root.left));
   
5.     res.add(root.val);
   
6.     res.addAll(inorder(root.right));
   
7.     return res;
   
8. }

复制代码

iterativeInorder(node)
    parentStack = empty stack
    while (not parentStack.isEmpty() or node != null)
        if (node != null)
            parentStack.push(node)
            node = node.left
        else
            noce = parentStack.pop()
            visit(node)
            node = node.right

1. public List<Integer> iterativeInorder(TreeNode root){
   
2.     List<Integer> res = new LinkedList<Integer>();
   
3.     if(root==null) return res;
   
4.     Stack<TreeNode> stack = new Stack<TreeNode>();
   
5.     while(!stack.isEmpty() || root!=null){
   
6.         if(root!=null){
   
7.             stack.push(root);
   
8.             root = root.left;
   
9.         }else{
   
10.             root = stack.pop();
    
11.             res.add(root.val);
    
12.             root = root.right;
    
13.        }
    
14.     }
    
15.     return res;
    
16. }
    

复制代码

LeetCode Link: https://oj.leetcode.com/problems/binary-tree-inorder-traversal/

Post-order：
postorder(node)
    if node == null then return
    postorder(node.left)
    postorder(node.right)
    visit(node)

1. public List<Integer> postorder(TreeNode root){
   
2.     List<Integer> res = new LinkedList<Integer>();
   
3.     if(root==null) return res;
   
4.     res.addAll(postorder(root.left));
   
5.     res.addAll(postorder(root.right));
   
6.     res.add(root.val);
   
7.     return res;
   
8. }

复制代码

iterativePostorder(node)
    parentStack = empty stack
    lastnodevisited = null
    while(not parentStack.isEmpty() or node !=null)
        if(node != null)
            parentStack.push(node)
            node = node.left
        else
            peeknode = parentStack.peek()
            if(peeknode.right!=null and lastnodevisited != peeknode.right)
                node = peeknode.right
            else
                visit(peeknode)
                lastnodevisited = parentStack.pop()

1. public List<Integer> iterativePostorder(TreeNode root){
   
2.     List<Integer> res = new LinkedList<Integer>();
   
3.     if(root==null) return res;
   
4.     Stack<TreeNode> stack = new Stack<TreeNode>();
   
5.     TreeNode lastNodeVisited = null;
   
6.     while(!stack.isEmpty()||root!=null){
   
7.         if(root!=null){
   
8.             stack.push(root);
   
9.             root = root.left;
   
10.         }else{
    
11.             TreeNode peekNode = stack.peek();
    
12.             if(peeknode.right!=null && peeknode.right!=lastNodeVisited){
    
13.                 root = peeknode.right;
    
14.             }else{
    
15.                 stack.pop();
    
16.                 res.add(peeknode.val);
    
17.                 lastNodeVisited = peeknode;
    
18.            }
    
19.         }
    
20.     }
    
21.     return res;
    
22. }

复制代码

LeetCode Link: https://oj.leetcode.com/problems/binary-tree-postorder-traversal/

good summary

赞，不错！！！！！