Binary Tree

Tree Tips

• worst case: 在考虑最差时间复杂度的时候，永远要记得考虑当树是一条线的时候

Traverse (DFS)

二叉树DFS的时候时间复杂度的计算方法是：看一下每个节点上处理的是复杂度 * 节点个数N 而递归的空间复杂度为O(h)

The addresses are removed from the stack when returning. This space is re-used when making a new call from a level closer to the root. So the maximum numbers of memory addresses on the stack at the same time is the tree height.

Recursive Traverse Solution

List<Integer> result = new ArrayList<Integer>();
traverse(root, result);

...
public void traverse(TreeNode root, List<Integer> list) {

    if (root == null) return;
    list.add(root.val);
    traverse(root.left, list);
    traverse(root.right, list);
}

Divide & Conquer

分解成子问题，左子树的traverse和右子树的traverse，用于递归和搜索

public List<Integer> traverse(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();
    //null or leaf
    if (root == null) return result;

    result.addAll(traverse(root.left));
    result.add(root.val);
    result.addAll(traverse(root.right));

    return result;
}

Non-recursive

• preoder(a.k.a DFS): stack每pop出一个值，就把下面一行的两个nodes压入

  • 因为是stack，所以应该倒过来，先压入右再压入左

  • push前需要做null check

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

• inorder

  • 把该点的左分支全部（while）压入直至节点没有左子树，第一次pop出来的点，加入结果，并讲cur指向其右分支。这时候cur可能存在两种情况：
    • 当右分支存在时候，保存当前根节点，继续将该当前节点的左分支全部压入，cur变成右分支中的最左点，同样pop出来，把cur指向其右边分支
    • 当这个点没有右边分支的时候，cur == null，直接pop获得他的根节点，继续将cur指向右分支

      public ArrayList<Integer> inorderTraversal(TreeNode root) {
          Stack<TreeNode> stack = new Stack<TreeNode>();
          ArrayList<Integer> result = new ArrayList<Integer>();
          TreeNode curt = root;
          while (curt != null || !stack.empty()) {
            while (curt != null) {
                stack.add(curt);
                curt = curt.left;
            }
            //no left sub tree, so now it's time for the root
            curt = stack.pop();
            result.add(curt.val);
            //deal with right subtree of the current node 
            curt = curt.right;
          }
          return result;
      }
      

• post order

  • 将root放入stack，然后将其左右也依次压入，这样出来的顺序是从上到下，从右到左，考虑到postorder是从下到上，从左到右，正好相反，这样只需要将最后的结果list翻转即可

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