hot100之二叉树上

二叉树的中序队列(094)

先看代码

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

复制代码

• 分析
  

通过stack保存二叉树遍历栈, 反序遍历栈节点
二叉树的最大深度(104)

先看代码

1. class Solution {
2.     int res = 0;
3.     public int maxDepth(TreeNode root) {
4.         if (root == null) return 0;
5.         int lefDepth = maxDepth(root.left);
6.         int rigDepth = maxDepth(root.right);
8.         return Math.max(lefDepth, rigDepth) + 1;
9.     }
10. }

复制代码

• 分析
  

递归调用自身

• 感悟
  

递归看的真的非常清爽, 写的也很清爽
翻转二叉树(226)

省略
对称二叉树(101)

省略
二叉树直径(543)

先看代码

1. class Solution {
2.     int res = 0;
3.     public int diameterOfBinaryTree(TreeNode root) {
4.         maxDepthBinaryTree(root);
5.         return res;
6.     }
8.     private int maxDepthBinaryTree(TreeNode node){
9.         if (node == null) return 0;
10.         int lefMax = maxDepthBinaryTree(node.left);
11.         int rigMax = maxDepthBinaryTree(node.right);
12.         res = Math.max(lefMax + rigMax, res);
13.         return Math.max(lefMax, rigMax) + 1;
14.     }
15. }

复制代码

• 分析
  

增加了一个全局res 参数用于记录最大长度, 可能算是贪心

• 感悟
  

递归要维持一致的变量与传递参数, 单凭借自身的传递参数无法解决问题, 所以引入了res 全局变量
二叉树的层序遍历(102)

先看代码

1. class Solution {
2.     public List<List<Integer>> levelOrder(TreeNode root) {
3.         List<List<Integer>> res  = new ArrayList<>();
4.         Deque<TreeNode> queue = new ArrayDeque<>();
6.         if (root != null) queue.addFirst(root);
7.         while (!queue.isEmpty()){
8.             int n = queue.size();
9.             List<Integer> layer = new ArrayList<>(n);
10.             for (int i = 0; i < n; i++){
11.                 TreeNode node = queue.removeLast();
12.                 layer.add(node.val);
13.                 if (node.left != null)  queue.addFirst(node.left);
14.                 if (node.right != null) queue.addFirst(node.right);
15.                
16.             }
17.             res.add(layer);
18.         }
20.         return res;
21.     }
22. }

复制代码

• 分析
  

通过双端队列, 左端入新端点, 右端出老端点, 每次for 循环, 一次性遍历完老端点
将有序数组转换为二叉搜索树(108)

略
验证二叉搜索树(098)

先看代码
[code]class Solution {    public boolean isValidBST(TreeNode root) {        return isValidBST(root, null, null);    }    private boolean isValidBST(TreeNode node, Integer max, Integer min){        if (node == null) return true;        int val = node.val;        if (max != null && val >= max) return false;        if (min != null && val