二叉树小结

二叉树

树的遍历(如何遍历，如何利用特性问题)

前序遍历（中前后）

递归

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val);             // 注意这一句inorder(root.right, list);}
}

迭代

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

中序遍历（前中后）

递归

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val);             // 注意这一句inorder(root.right, list);}
}

迭代

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

后序遍历（前后中）

递归

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val);             // 注意这一句}
}

迭代

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

利用遍历的特性

• 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
• 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
• 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。