树的基础算法

一、基础 + 遍历

144. 二叉树的前序遍历

经典二叉树前序遍历

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

94. 二叉树的中序遍历

left -> node -> right

和非递归先序遍历类似，唯一区别是考察到当前节点时，并不知节输出该节点。

public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      Stack<TreeNode> stack = new Stack();
  		
  		while (root != null || !stack.isEmpty()) {
        while (root != null) {
          	stack.push(root);
          	root = root.left;
        }
        root = stack.pop();
        res.add(root.val);
        root = root.right;
      }
  
  		return res;
}

145. 二叉树的后序遍历

left -> right -> node

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      Stack<TreeNode> stack = new Stack();
      if (root != null) stack.push(root);
      while(!stack.isEmpty()) {
        root = stack.pop();
        res.add(0, root.val); // 反向 add
        if (root.left != null) stack.push(root.left);
        if (root.right != null) stack.push(root.right);
      }
      return res;
    }
}

102. 二叉树的层序遍历

​