树的遍历总结

树的节点:

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
    }
}

树节点

先序:１２４６７８３５
先序走的 /_ 形状

中序:４７６８２１３５
中序走 /\ 形状

后序：７８６４２５３１
后序走 _\ 形状

树的遍历

递归无返回值遍历

先序:

public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

中序:

public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        preOrder(root.left);
        System.out.println(root.val);
        preOrder(root.right);
    }

后序:

public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.println(root.val);
}

递归有返回值遍历

注意所有的遍历走过了路径都是相同的,只是输出(操作)的延迟问题,也可以在依靠树遍历的回溯完成操作,递归操作是对当前节点的不同状态下不同情况的考虑,不需要考虑上下父子关系

1. 判断是不是二茬排序树

// 使用包装类可以传入数值为null 的情况,这样便于处理第一次来进行区分

// 通过验证子树的数值范围进行优化为子问题
    public boolean isValidBST2(TreeNode root) {
        return helper(root,null,null);
    }

    // 后序遍历分析
    // 使用Integer可以传入值为null
    private boolean helper(TreeNode root, Integer low, Integer hight) {
        if (root == null){
            return true;
        }
        if (!helper(root.left,low,root.val)){
            return false;
        }
        if (!helper(root.right,root.val,hight)){
            return false;
        }
        if (low != null && root.val <= low){
            return false;
        }
        if (hight != null && root.val >= hight){
            return false;
        }
        return true;
    }

2. 判断是否是对称二叉树
   // 对称二叉树

public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        boolean symmetric = isSymmetric(root.left, root.right);
        return symmetric;
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null){
            return true;
        }
        if (left == null || right == null){
            return false;
        }
        boolean l = isSymmetric(left.left, right.right);
        if (l == false){
            return false;
        }
        boolean r = isSymmetric(left.right, right.left);
        if (r == false){
            return false;
        }
        if (left.val != right.val){
            return false;
        }
        return true;
    }

有返回值的递归遍历有两种情况: 1. 要维持一个树的结构,最后返回根节点,即返回值是TreeNode

那么就把这个 TreeeNode.left = 递归 TreeNode.right = 递归 .2 如果返回的是数值类, 每一个子树都要进行判断是否,在子树中已经完成可以直接返回

递归中是否右参数传递

 List<List<Integer>> result = new ArrayList<>();
    // 使用递归+ 第几个list来表明层
    public List<List<Integer>> levelOrder1(TreeNode root) {
        levelOrder(root,0);
        return result;
    }

    private void levelOrder(TreeNode root, int i) {
        if (root == null){
            return;
        }
        List<Integer> list = null;
        if (i == result.size()){
            list = new ArrayList<>();
            result.add(list);
        }
        result.get(i).add(root.val);
        levelOrder(root.left,i+1);
        levelOrder(root.right,i+1);
    }

如果右参数传递,同时参数不需要和左右子树进行交互

如果需要和左右子树进行交互则,直接赋值即可

 private String reSerialize(TreeNode root, String str) {
        if (root == null){
            str += "#"+" ";
        }else {
            str += root.val + " ";
            str = reSerialize(root.left,str);
            str = reSerialize(root.right,str);
        }
        return str;
    }
    

自顶向下

在遍历左右孩子结点前更新返回值

1. return specific value for null node
2. update the answer if needed                      // anwer <-- params
3. left_ans = top_down(root.left, left_params)      // left_params <-- root.val, params
4. right_ans = top_down(root.right, right_params)   // right_params <-- root.val, params
5. return the answer if needed                      // answer <-- left_ans, right_ans

1. return if root is null
2. if root is a leaf node:
3.      answer = max(answer, depth)         // update the answer if needed
4. maximum_depth(root.left, depth + 1)      // call the function recursively for left child
5. maximum_depth(root.right, depth + 1)     // call the function recursively for right child

自底向上的遍历

根据返回值进行更新来进行，完成递归

1. return specific value for null node
2. left_ans = bottom_up(root.left)          // call function recursively for left child
3. right_ans = bottom_up(root.right)        // call function recursively for right child
4. return answers                           // answer <-- left_ans, right_ans, root.va

// 后序遍历的回溯

public int maxDepth(TreeNode root) {
        // 如果是null
        if (root == null){
            return 0;
        }
        // 如果没孩子
        if (root.left == null && root.right == null){
            return 1;
        }
        // 有孩子
        return Math.max(maxDepth(root.left),maxDepth(root.right)) +1;
    }

非递归遍历

二叉树的遍历都是可以用栈来进行模拟,因为递归就是在jvm中内部栈进行操作

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        // 找到左子树最左边
        while (root != null){
            stack.push(root);
            root = root.left;
        }
        while (!stack.empty()) {
            // 弹出添加结果集,模仿回溯
            TreeNode node = stack.pop();
            result.add(node.val);
            // 找到右节点最左
            if (node.right != null){
                TreeNode right = node.right;
                while (right != null){
                    stack.push(right);
                    right = right.left;
                }
            }
        }
        return result;
    }

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

// 莫里斯中序遍历

1. 将当前节点cur初始化为根节点
2. while cur不为null

• 1. 如果cur没有左节点

•   cur添加到输出
  

•   进入右子树 cur = cur.right
  

• 2. 否则
• 使用pre找打cur的前驱节点,使cur称为pre的右节点
• tmp临时存储cur, cur = cur.left
• tmp.left = null 这样cur的左为空那么就会被遍历

 public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        TreeNode cur = root;
        TreeNode pre = null;
        while (cur != null){
            if (cur.left == null){
                result.add(cur.val);
                cur = cur.right;
            }else{
                pre = cur.left;
                while (pre.right != null){
                    pre = pre.right;
                }
                pre.right = cur;
                TreeNode tmp = cur;
                cur = cur.left;
                tmp.left = null;
            }
        }
        return result;
    }

// 二叉树的所有可能组合

递归的思想
采用后序遍历

1. 当left > right 说明该节点直接为null,那么它所有可能都为null,
2. 以i作为根节点,产生左子树的所有可能,产生右子树所有可能
3. 给当前节点i,双层循环安装它所有可能的左右子树

public List<TreeNode> generateTrees(int n) {
         if (n < 1){
             return null;
         }
        LinkedList<TreeNode> res = generateTree(1, n);
        return res;
    }

    private LinkedList<TreeNode> generateTree(int left, int right) {
        LinkedList<TreeNode> all_trees = new LinkedList<>();
        if (left > right){
            // 这里必须添加null 因为 left<right 无法生成树
            all_trees.add(null);
            return all_trees;
        }
        // 因为二叉树的所有组合方式无非左子树,右子树两个列表,所有二叉树的所有情况可以通过两重for循环
        for (int i=left;i<=right;i++){
            // 采用后序遍历,找出子树所有可能
            LinkedList<TreeNode> left_trees = generateTree(left, i - 1);
            LinkedList<TreeNode> right_trees = generateTree(i + 1, right);
            for (TreeNode l:left_trees) {
                for (TreeNode r:right_trees) {
                    TreeNode cur = new TreeNode(i);
                    cur.left = l;
                    cur.right = r;
                    all_trees.add(cur);
                }
            }
        }
        return all_trees;
    }

// 增加缓存进行剪枝,可以提前返回已缓存的结果

public List<TreeNode> generateTrees2(int n) {
        if (n < 1){
            return new ArrayList<TreeNode>();
        }
        HashMap<String,List<TreeNode>> map = new HashMap<>();
        List<TreeNode> res = generateTree2(1, n,map);
        return res;
    }

    private List<TreeNode> generateTree2(int left, int right,HashMap<String,List<TreeNode>> map) {
        LinkedList<TreeNode> all_trees = new LinkedList<>();
        if (left > right){
            // 这里必须添加null 因为 left<right 无法生成树
            all_trees.add(null);
            return all_trees;
        }
        String key = left +","+right;
        if (map.containsKey(key)){
            return map.get(key);
        }
        // 因为二叉树的所有组合方式无非左子树,右子树两个列表,所有二叉树的所有情况可以通过两重for循环
        for (int i=left;i<=right;i++){
            // 采用后序遍历,找出子树所有可能
            List<TreeNode> left_trees = generateTree2(left, i - 1,map);
            List<TreeNode> right_trees = generateTree2(i + 1, right,map);
            for (TreeNode l:left_trees) {
                for (TreeNode r:right_trees) {
                    TreeNode cur = new TreeNode(i);
                    cur.left = l;
                    cur.right = r;
                    all_trees.add(cur);
                }
            }
        }
        map.put(key,all_trees);
        return all_trees;
    }

// 不同二叉树的个数

从 1~n构建二叉树

1. 让每一个节点作为根节点
2. 那么它右边作为右子树,左边作为左子树
   G(n) = F(i,n)
   G(n) 代表n个节点生成不同二叉树个数, F(i,n) 以 i 作为节点生成的二叉树
   F(i,n) = G(i-1) * G(n-i)

所以 G(n) = 求和i从1到n G(i-1) * G(n-i)

public int numTrees(int n){
        if (n < 2){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[0] = 1;dp[1] = 1;
        for (int i=2;i<=n;i++){
            dp[i] = 0;
            for (int k=1;k<=i;k++){
                dp[i] += (dp[k-1]*dp[i-k]);
            }
        }
        return dp[n];
}

// 类似与 F(n) = f(0)(n) + F(1)F(n-1) + ... + F(n)F(0) 都属于卡特兰数

Cn+1 = 2*(2n+1)/n+2 *Cn

 public int numTrees(int n){
        long C = 1;
        for (int i=0;i<n;i++){
            // 不能把乘号写在除号后面,要不 可能会乘到分母上
            C = C * 2* (2*i+1)/(i + 2);
        }
        return (int) C;
    }

// 验证二茬搜索树
非递归更好理解,会更快的做出来
使用中序遍历,然后上一个节点大于等于后一个返回false,
最后返回true

public boolean isValidBST(TreeNode root) {
         // 用来标注之前节点
         TreeNode pre = null;
         Stack<TreeNode> stack = new Stack<>();
         if (root == null){
             return true;
         }
         TreeNode cur = root;
         while (!stack.empty() || cur != null){
             if (cur != null){
                 stack.push(cur);
                 cur = cur.left;
             }else {
                 cur = stack.pop();
                 if (pre != null && pre.val >= cur.val){
                      return false;
                 }
                 pre = cur;
                 cur = cur.right;
             }
         }
         return true;
    }

// 在递归的验证过程中一定要使用全局变量来保存pre值这样可以快速生效在左子树的递归中而避免只有右子树生效
如果没有右子树,那么pre的修改将不会生效

 TreeNode pre = null;
    public boolean inOrder(TreeNode root){
        if (root.left != null) {
            boolean l = inOrder(root.left);
            if (l == false){
                return false;
            }
        }
        if (pre != null && pre.val >= root.val){
            return false;
        }
        pre = root;
        if (root.right != null) {
            boolean r = inOrder(root.right);
            if (r == false){
                return false;
            }
        }
        return true;
    }
     public boolean isValidBST(TreeNode root) {
         if (root == null){
             return true;
         }
         return inOrder(root);
    }

// 使用包装类可以传入数值为null 的情况,这样便于处理第一次来进行区分

// 通过验证子树的数值范围进行优化为子问题
    public boolean isValidBST2(TreeNode root) {
        return helper(root,null,null);
    }

    // 后序遍历分析
    // 使用Integer可以传入值为null
    private boolean helper(TreeNode root, Integer low, Integer hight) {
        if (root == null){
            return true;
        }
        if (!helper(root.left,low,root.val)){
            return false;
        }
        if (!helper(root.right,root.val,hight)){
            return false;
        }
        if (low != null && root.val <= low){
            return false;
        }
        if (hight != null && root.val >= hight){
            return false;
        }
        return true;
    }

// 恢复二叉树

// 恢复二茬搜索树 , 主要问题是找到两个错位节点
    // 如果在中序遍历中出现两次降序的节点,那么两个错误节点为第一次的较大节点,第二次的较小节点
    // 如果只存在一次的降序,那么两个节点就是该位置节点
    // 首先 找到两个节点 然后进行交换
    // 树中两个节点的交换
    public void recoverTree(TreeNode root) {
         Stack<TreeNode> stack = new Stack<>();
         if (root == null){
             return;
         }
         TreeNode cur = root;
         TreeNode pre = null;
         TreeNode tmp1 = null;
         TreeNode tmp2 = null;
         int count = 0;
         while (!stack.empty() || cur != null){
             if (cur != null){
                 stack.push(cur);
                 cur = cur.left;
             }else {
                 cur = stack.pop();
                 // 操作
                 if (pre != null && pre.val >= cur.val){
                     if (count == 0){
                         tmp1 = pre;
                         tmp2 = cur;
                         count++;
                     }else {
                         tmp2 = cur;
                     }
                 }
                 pre = cur;
                 cur = cur.right;
             }
         }
         int t = tmp1.val;
         tmp1.val = tmp2.val;
         tmp2.val = t;
    }

// 对称二叉树

public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        boolean symmetric = isSymmetric(root.left, root.right);
        return symmetric;
    }

    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null){
            return true;
        }
        if (left == null || right == null){
            return false;
        }
        boolean l = isSymmetric(left.left, right.right);
        if (l == false){
            return false;
        }
        boolean r = isSymmetric(left.right, right.left);
        if (r == false){
            return false;
        }
        if (left.val != right.val){
            return false;
        }
        return true;
    }

// 两棵树是否相同
递归判断

 public boolean isSameTree(TreeNode p, TreeNode q) {
         if (p == null && q == null){
             return true;
         }
         if (p == null || q == null){
             return false;
         }
        boolean l = isSameTree(p.left, q.left);
         if (l == false){
             return false;
         }
        boolean r = isSameTree(p.right, q.right);
         if (r == false){
             return false;
         }
         if (p.val != q.val){
             return false;
         }
         return true;
    }

// 使用迭代判断相同的树

 public boolean isSameTree(TreeNode p, TreeNode q) {
        // 使用队列进行迭代判断
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()){
            p = queue.poll();
            q = queue.poll();
            if (q == null && p == null){
                // continue进行再次迭代
                continue;
            }
            if (q == null || p == null){
                return false;
            }
            queue.offer(p.left);queue.offer(q.left);
            queue.offer(p.right);queue.offer(q.right);
            if (q.val != p.val){
                return false;
            }
        }
        return true;
    }

// 使用外置变量 + 当前的list数量 进行层次遍历

 List<List<Integer>> result = new ArrayList<>();
    // 使用递归+ 第几个list来表明层
    public List<List<Integer>> levelOrder1(TreeNode root) {
        levelOrder(root,0);
        return result;
    }

    private void levelOrder(TreeNode root, int i) {
        if (root == null){
            return;
        }
        List<Integer> list = null;
        if (i == result.size()){
            list = new ArrayList<>();
            result.add(list);
        }
        result.get(i).add(root.val);
        levelOrder(root.left,i+1);
        levelOrder(root.right,i+1);
    }

使用双队列进行交换进行层次遍历

 // 使用 双队列交换实现树的层次遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> tmp = new LinkedList<>();
        if (root == null){
            return result;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            while (!queue.isEmpty()){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) tmp.offer(node.left);
                if (node.right != null) tmp.offer(node.right);
            }
            result.add(list);
            Queue<TreeNode> t = queue;
            queue = tmp;
            tmp = t;
        }
      return result;
      ```

或者不进行交换,计算每次添加队列的长度
从第一次开始计算当前队列的长度,然后每次弹出总是弹出上次记录的长度

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int level = 0;
        if (root == null){
            return result;
        }
        queue.offer(root);
        while (!queue.isEmpty()){
            if (level == result.size()){
                result.add(new ArrayList<Integer>());
            }
            int level_len = queue.size();
            for (int i=0;i<level_len;i++){
                TreeNode node = queue.poll();
                result.get(level).add(node.val);
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
            level++;
        }
      return result;
    }

// 使用栈进行二叉树的锯齿层次遍历
// 不能使用队列的原因是因为,队列只能对单个节点的左右进行反转,但是不能对整层进行反转
// 同时使用栈也必须使用双栈的原因是,一层是正序,一层逆序,但是后加的会放到栈顶,而没办法区分层次

 // 使用 双栈交换实现树的层次遍历
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> tmp = new Stack<>();
        if (root == null){
            return result;
        }
        int flag = 1;
        stack.push(root);
        while (!stack.empty()){
            List<Integer> list = new ArrayList<Integer>();
            while (!stack.empty()){
                TreeNode node = stack.pop();
                list.add(node.val);
                if (flag == 1){
                    if (node.left != null) {
                        tmp.push(node.left);
                    }
                    if (node.right != null){
                        tmp.push(node.right);
                    }
                }else {
                    if (node.right != null){
                        tmp.push(node.right);
                    }
                    if (node.left != null) {
                        tmp.push(node.left);
                    }
                }
            }
            result.add(list);
            Stack<TreeNode> t = tmp;
            tmp = stack;
            stack = t;
            flag = -flag;
        }
      return result;
    }

// 使用LinkedList 的 addFirst化解尴尬

List<List<Integer>> result = new ArrayList<>();
     private void levelOrder(TreeNode root, int i) {
        if (root == null){
            return;
        }
        LinkedList<Integer> list = null;
        if (i == result.size()){
            list = new LinkedList<>();
            result.add(list);
        }
        // 使用list的addFirst一秒化解尴尬
        if (i % 2 == 0) {
            result.get(i).add(root.val);
        }else {
            LinkedList<Integer> linkedList = (LinkedList<Integer>) result.get(i);
            linkedList.addFirst(root.val);
        }
        levelOrder(root.left,i+1);
        levelOrder(root.right,i+1);
    }
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
      levelOrder(root,0);
      return result;
    }

// 从前序和中序建立二叉树

任然属于大问题,转小问题的子类优化问题
实际上构建二叉树只需要前序遍历或者中序遍历就可以
那么另一颗,只用于查找子树的大小

public TreeNode buildTree(int[] preorder, int[] inorder) {
         return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    private TreeNode buildTree(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {
        if (s1 > e1 || s2 > e2){
            return null;
        }
        int val = preorder[s1];
        TreeNode root = new TreeNode(val);
        int index = findNum(inorder,val,s2,e2);
        int left_size = index - s2;
        int right_start = s1 + left_size;
        root.left = buildTree(preorder,s1+1,right_start,inorder,s2,index-1);
        root.right = buildTree(preorder,right_start+1,e1,inorder,index+1,e2);
        return root;
    }

    private int findNum(int[] inorder, int val,int s2,int e2) {
        for (int i=s2;i<=e2;i++){
            if (val == inorder[i]){
                return i;
            }
        }
        return -1;
    }

// 使用 pre_index = 0 代表取前驱节点中的值,因为前驱节点中根节点是简单的递增

    int pre_index = 0;
    HashMap<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
         int index = 0;
        for (int x:inorder) {
            map.put(x,index++);
        }
        return buildTree(preorder,0,inorder.length-1);
    }

    private TreeNode buildTree(int[] preorder, int left, int right) {
        if (left > right){
            return null;
        }
        int val = preorder[pre_index];
        TreeNode root = new TreeNode(val);
        Integer index = map.get(val);
        pre_index++;
        root.left = buildTree(preorder,left,index-1);
        root.right = buildTree(preorder,index+1,right);
        return root;
    }

// 从下层的层次遍历只需要将add(0,list) 或者为 addFirst(list)

 public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int level = 0;
        while(!queue.isEmpty()){
            if (level == result.size()){
                result.addFirst(new ArrayList<Integer>());
            }
            int level_len = queue.size();
            for (int i=0;i<level_len;i++){
                TreeNode node = queue.poll();
                result.get(0).add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
           level++;
        }
        return result;
    }

// 将有序数组转化为平衡的二叉排序树

 // 将有序数组转化为高度平衡的二叉搜索数，主要找到根节点，左右子树大小相同，因为有序，那么一定是中间结点
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0){
            return null;
        }
        return sortedArrayToBST(nums,0,nums.length-1);
    }
    // 采用树的先序遍历
    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left > right){
            return null;
        }
        int mid = left + (right - left)/2;
        int val = nums[mid];
        TreeNode root = new TreeNode(val);
        
        root.left = sortedArrayToBST(nums,left,mid-1);
        root.right = sortedArrayToBST(nums,mid+1,right);
        return root;
    }

// 判断树是不是平衡二叉树
// 可以先写好计算树高度的算法，然后后序遍历，在最后在计算左右子树的高度是否合法
// 相当于从先序的计算平衡二叉树

 public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        if (root.left != null) {
            boolean l = isBalanced(root.left);
            if (l == false){
                return false;
            }
        }
        if (root.right != null){
            boolean r = isBalanced(root.right);
            if (r == false){
                return false;
            }
        }
        int lh = treeHight(root.left);
        int rh = treeHight(root.right);
        if (Math.abs(lh-rh)>=2){
            return false;
        }
        return true;
    }

    public int treeHight(TreeNode root) {
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return Math.max(treeHight(root.left),treeHight(root.right))+1;
    }

//对上面的算法进行优化后

 public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        return Math.abs(treeHight(root.right) - treeHight(root.left)) < 2?
                isBalanced(root.left)&&isBalanced(root.right):false;
    }

    public int treeHight(TreeNode root) {
        if (root == null){
            return 0;
        }
        return Math.max(treeHight(root.left),treeHight(root.right))+1;
    }

// 仔细思考后可以直接剪枝优化为树的高度的算法
// 用-1来表明树是不平衡二叉树，直接返回-1，相当于对树的高度算法进行了剪枝

 // 使用-1代表不平衡
    public boolean isBalanced2(TreeNode root) {
        if (root == null){
            return true;
        }
        return helperHight(root) != -1;
    }

    private int helperHight(TreeNode root) {
        if (root == null){
            return 0;
        }
        int l = helperHight(root.left);
        if (l == -1){
            return -1;
        }
        int r = helperHight(root.right);
        if (r == -1){
            return -1;
        }
       return Math.abs(l-r) <2?Math.max(l,r)+1:-1;
    }

// 计算二叉树的最小深度
只需要将root 为null情况置为无穷大，加上
左右子树等于null的节点，那么它就只会去寻找左右子树为null的情况

public int minDepth(TreeNode root) {
       if (root == null){
           return 0;
       }
        if (root.left == null && root.right == null){
            return 1;
        }
       return Math.min(helper(root.left),helper(root.right))+1;
    }

    private int helper(TreeNode root) {
        if (root == null){
            return Integer.MAX_VALUE;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        return Math.min(helper(root.left),helper(root.right))+1;
    }

// 路径总和
这里递归有返回值遍历,带有返回值的遍历其实就是把函数体里面的内容当做为对当前节点的操作
那么对应左右子树返回的值也进行判断+返回
//后减当前值

public boolean hasPathSum(TreeNode root, int sum) {
        
        if (root == null){
            return false;
        }

        if (root.left == null && root.right == null){
            if (sum == root.val){
                return true;
            }
        }

         if (root.left != null){
             boolean l = hasPathSum(root.left, sum - root.val);
             if (l == true){
                 return true;
             }
         }
         if (root.right != null){
             boolean r = hasPathSum(root.right, sum - root.val);
             if (r == true){
                 return true;
             }
         }
         return false;
    }

// 简化上面的算法

 public boolean hasPathSum2(TreeNode root, int sum) {
        if (root == null){
            return false;
        }
        sum -= root.val;
        if (root.left == null && root.right == null){
            if (sum == 0){
                return true;
            }
        }
        // 这里只要左右子树中存在正好合适就行所以使用||
        return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
    }

// 使用树的先序遍历进行计算

// 使用 DFS 计算
    public boolean hasPathSum3(TreeNode root, int sum) {
         if (root == null){
             return false;
         }
         Stack<TreeNode> stack = new Stack<>();
         Stack<Integer> sum_stack = new Stack<>();
         sum -= root.val;
         stack.push(root);
         sum_stack.push(sum);
         while (!stack.empty()){
             TreeNode p = stack.pop();
             sum = sum_stack.pop();
             if (p.left == null && p.right == null){
                 if (sum == 0){
                     return true;
                 }
             }
             if (p.right != null){
                 stack.push(p.right);
                 sum_stack.push(sum - p.right.val);
             }
             if (p.left != null){
                 stack.push(p.right);
                 sum_stack.push(sum - p.left.val);
             }
         }
       return false;
    }

/// 树路径总和

1. 用一个变量记录当前的访问路径的节点列表
2. 如果当前为根节点同时sum 递减为0 说明确实是该路径加入结果集,如果是根节点就会回溯,那么
   curList中删除最后节点
3. 使用后序进行回溯操作,因为左和右就会回溯,在后序遍历的位置加上 curList.remove()

List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum2(TreeNode root, int sum){
        helperPath(root,sum, new ArrayList<Integer>());
        return result;
    }

    private void helperPath(TreeNode root, int sum, ArrayList<Integer> curList) {
        if (root == null){
            return;
        }
        sum -= root.val;
        curList.add(root.val);
        if (root.left == null && root.right == null){
            if (sum == 0){
                result.add(new ArrayList<Integer>(curList));
            }
            curList.remove(curList.size()-1);
            return;
        }
        helperPath(root.left,sum,curList);
        helperPath(root.right,sum,curList);
        curList.remove(curList.size()-1);
    }

// 使用非递归求解路径总和

1. 使用new ArrayList<>(list); 来添加list的拷贝
2. 使用 path_stack来缓存每条路的,每个左右节点是不同的list所有在添加左list前push一个新的当前list的拷贝

 public List<List<Integer>> pathSum(TreeNode root, int sum) {
         List<List<Integer>> result = new ArrayList<>();
         if (root == null){
             return result;
         }
         List<Integer> subList = new ArrayList<>();
         
         Stack<TreeNode> stack = new Stack<>();
         Stack<Integer> num_stack = new Stack<>();
         Stack<List<Integer>> path_stack = new Stack<>();
         
         int total = 0;
         while (root != null || !stack.empty()){
             if (root != null){
                 total += root.val;
                 subList.add(root.val);
                 if (total == sum && root.left == null && root.right == null){
                     result.add(new ArrayList<>(subList));
                 }
                 num_stack.push(total);
                 stack.push(root.right);
                 path_stack.push(new ArrayList<>());
                 root = root.left;
             }else {
                 root = stack.pop();
                 total = num_stack.pop();
                 subList = path_stack.pop();
             }
         }
         return result;
    }

// 将二叉树转换为列表
// 前序遍历直接转换

1. 如果没有左节点不用转换直接下一个 cur = cur.right
2. 如果有左节点,找到左节点的最右边
3. 将原来的最右变挂到最右节点上
4. 将左子树变为右子树
5. 将左子树变为null

 // 使用先序遍历将二叉树转换为链表,(只有右子树)
    //
    public void flatten(TreeNode root) {

        if (root == null){
            return;
        }
        TreeNode cur = root;
        TreeNode pre = null;
        while (cur != null){
            if (cur.left == null){
                cur = cur.right;
            }else {
               // 找到左子树最右边
                pre = root.left;
                while (pre.right != null){
                    pre = pre.right;
                }
                // 将原来的右子树接到左子树最右边
                pre.right = cur.right;
                //左子树插入右子树地方
                cur.right = cur.left;
                cur.left = null;
                // 考虑下一个节点
                cur = cur.right;
            }
        }
    }

// 填充每一个节点的下一个右侧节点为NULL
实际上就是层次遍历的问题改进版
// 使用迭代进行解决

public Node connect(Node root) {
       if (root == null){
           return null;
       }
       Queue<Node> queue = new LinkedList<>();
       queue.add(root);
       while (!queue.isEmpty()){
           int level_len = queue.size();
           Node node = queue.poll();
           if (node.left != null)
           queue.offer(node.left);
           if (node.right != null)
           queue.offer(node.right);
           for (int i=1;i<level_len;i++){
               Node tmp = queue.poll();
               if (tmp.left != null)
               queue.offer(tmp.left);
               if (tmp.right != null)
               queue.offer(tmp.right);
               node.next = tmp;
               node = node.next;
           }
           node.next = null;
       }
       return root;
    }

// 使用递归进行解决
// 1. 将两个子树中间进行合上,

2. 递归访问,左右子树,左右子树右分为中间和两边,然后再进行合上

public Node connect2(Node root) {
        if (root == null){
            return null;
        }
        Node left = root.left;
        Node right = root.right;
        // 把中间的合上
        while (left != null){
            left.next = right;
            left = left.right;
            right = right.left;
        }
        connect(root.left);
        connect(root.right);
        return root;
    }

/// 不使用递归也不用其他空间
// 因为是满二叉树,cur记录的下一层的第一个左孩子节点
pre记录的是父节点
让父的左孩子指向右还是,如果pre的next不为null说明pre存在兄弟
则pre的right指向兄弟的左
pre 指向兄弟
pre 变为下一层的起始节点
cur 指向下一层的最左节点

public Node connect3(Node root) {
        if (root == null){
            return root;
        }
        Node cur = root;
        Node pre = null;
        while (cur != null){
            while (pre != null){
                pre.left.next = pre.right;
                if (pre.next != null){
                    pre.right.next = pre.next.left;
                }
                pre = pre.next;
            }
            pre = cur;
            cur = cur.left;
        }
        return root;
    }

// 使用next来代替队列

 // 使用next代替队列
    public Node connect4(Node root) {
        // 将根节点设置为队尾
        Node last = root;
        while (last != null){
            // 如果当前节点没有孩子节点,访问下一个节点
            while (last != null && last.left == null && last.right == null){
                last = last.next;
            }
            if (last == null) {
                break;
            }
            Node cur = null;
            for (Node i = last;i != null;i = i.next){
                if (i.left != null){
                    if (cur != null){
                        cur.next = i.left;
                    }
                    cur = i.left;
                }
                if (i.right != null){
                    if (cur != null){
                        cur.next = i.right;
                    }
                    cur = i.right;
                }
            }
            last = last.left != null?last.left:last.right;
        }
        return root;
    }

// 只包含两种情况
一条之路上的两点之和/ 或者还是 /\ 型 三点之和

 int max_sum = Integer.MIN_VALUE;
    // 二叉树的最大的路径和 可以是 一条之路上的两点之和/ 或者还是 /\ 型 三点之和

    public int maxPathSum(TreeNode root) {
         maxGain(root);
         return max_sum;
    }

    private int maxGain(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left_max = Math.max(maxGain(root.left),0);
        int right_max = Math.max(maxGain(root.right),0);

        int cur_max = root.val + left_max + right_max;

        max_sum = Math.max(cur_max,max_sum);

        return root.val + Math.max(right_max,left_max);
    }

// 求根到叶子节点的路径之和
// 使用递归的方法求

 int res = 0;
    public int sumNumbers2(TreeNode root) {
        if (root == null){
            return 0;
        }
        helperSum(root,0);
        return res;
    }

    private void helperSum(TreeNode root, int sum) {
        sum = sum * 10 + root.val;
        if (root.left == null && root.right == null){
            res += sum;
        }
        if (root.left != null)
            helperSum(root.left,sum);
        if (root.right != null)
            helperSum(root.right,sum);
    }

// 使用非递归求根到叶子节点的路径之和

 // 其实就是先序遍历,在进行右节点是保存一个拷贝值
    public int sumNumbers(TreeNode root) {
        if (root == null){
            return 0;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer>  num_stack = new Stack<>();
        // 让p指向 root
        stack.push(root);
        num_stack.push(root.val);
        int res = 0;
        int num = 0;
        while (!stack.empty()){
            TreeNode p = stack.pop();
            num = num_stack.pop();
            if (p.left == null && p.right == null){
                res += num;
            }
            if (p.right != null){
                stack.push(p.right);
                num_stack.push(num * 10 + p.right.val);
            }
            if (p.left != null){
                stack.push(p.left);
                num_stack.push(num * 10 + p.left.val);
            }
        }
        return res;
    }
    ```
// 使用分治思想求根到叶子节点的路径之和

// 使用分治思想
public int sumNumbers3(TreeNode root){
if (root == null){
return 0;
}
return sumhelper(root,0);
}

private int sumhelper(TreeNode root, int curSum) {
    int sum = curSum * 10 + root.val;
    if (root.left == null && root.right == null){
        return sum;
    }
    int ans = 0;
    if (root.left != null){
        ans += sumhelper(root.left,sum);
    }
    if (root.right != null){
        ans += sumhelper(root.right,sum);
    }
    return ans;
}

// 二叉树的递归前序遍历

 List<Integer> resList = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null){
            return resList;
        }
        preOrder(root);
        return resList;
    }

    private void preOrder(TreeNode root) {
        if (root == null){
            return;
        }
        resList.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

// 非递归的前序遍历

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

// 不使用栈进行前序遍历二叉树

1. 如果当前节点没有左节点,直接将当前节点添加到结果集,并访问右节点
2. 否则,找到当前节点的前序回溯的前驱, 同时判断是否以及标记(将前驱的右节点指向当前节点)
3. 没有标记,说明左子树没访问添加当前节点让前驱指向当前节点,访问左节点
4. 否则 ,说明左子树已经访问,前驱断开,访问右节点

 public List<Integer> preorderTraversal4(TreeNode root){
        LinkedList<Integer> result = new LinkedList<>();
        TreeNode node = root;
        while (node!=null){
            if (node.left == null){
                result.add(node.val);
                node = node.right;
            }else {
                TreeNode pre = node.left;
                while ((pre.right != null) && (pre.right != node)){
                    pre = pre.right;
                }
                if (pre.right == null){
                    result.add(node.val);
                    pre.right = node;
                    node = node.left;
                }else {
                    pre.right = null;
                    node = node.right;
                }
            }
        }
        return result;
    }

// 使用递归实现后序遍历

List<Integer> res1 = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
         if (root == null){
             return res1;
         }
         posOrder(root);
         return res1;
    }

    private void posOrder(TreeNode root) {
        if (root == null){
            return;
        }
        posOrder(root.left);
        posOrder(root.right);
        res1.add(root.val);
    }

// 使用栈+ addFirst 实现后序遍历

// 使用栈+ addFirst 实现后序遍历
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()){
            TreeNode node = stack.pop();
            res.add(0,node.val);

            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        return res;
    }

// todo 后序morris遍历

public List<Integer> postorderTraversal3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            // 情况 1
            if (cur.left == null) {
                cur = cur.right;
            } else {
                // 找左子树最右边的节点
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }
                // 情况 2.1
                if (pre.right == null) {
                    pre.right = cur;
                    cur = cur.left;
                }
                // 情况 2.2,第二次遍历节点
                if (pre.right == cur) {
                    pre.right = null; // 这里可以恢复为 null
                    //逆序
                    TreeNode head = reversList(cur.left);
                    //加入到 list 中，并且把逆序还原
                    reversList(head, list);
                    cur = cur.right;
                }
            }
        }
        TreeNode head = reversList(root);
        reversList(head, list);
        return list;
    }

    private TreeNode reversList(TreeNode head) {
        if (head == null) {
            return null;
        }
        TreeNode tail = head;
        head = head.right;

        tail.right = null;

        while (head != null) {
            TreeNode temp = head.right;
            head.right = tail;
            tail = head;
            head = temp;
        }

        return tail;
    }

    private TreeNode reversList(TreeNode head, List<Integer> list) {
        if (head == null) {
            return null;
        }
        TreeNode tail = head;
        head = head.right;
        list.add(tail.val);
        tail.right = null;

        while (head != null) {
            TreeNode temp = head.right;
            head.right = tail;
            tail = head;
            list.add(tail.val);
            head = temp;
        }
        return tail;
    }

// 二叉树的右视图

  // 典型二叉树层次遍历 ,当访问到每层的最后一个节点保存即可
    public List<Integer> rightSideView(TreeNode root) {
         List<Integer> result = new ArrayList<>();
         if (root == null){
             return result;
         }
         Queue<TreeNode> queue = new LinkedList<>();
         queue.offer(root);
         while (!queue.isEmpty()){
             int level_len = queue.size();
             for (int i=0;i<level_len;i++){
                 TreeNode node = queue.poll();
                 if (i == level_len -1){
                     result.add(node.val);
                 }
                 if (node.left != null){
                     queue.offer(node.left);
                 }
                 if (node.right != null){
                     queue.offer(node.right);
                 }
             }
         }
         return result;
    }

通过先序遍历,来先遍历右子树来保存每一层的第一个值

// 先序遍历 右子树 ,保存每一个层的第一个节点
    public List<Integer> rightSideView2(TreeNode root) {
         List<Integer> res = new ArrayList<>();
         if (root == null){
             return res;
         }
         preRightOrder(root,res,0);
         return res;
    }

    private void preRightOrder(TreeNode root, List<Integer> res, int level) {
        if (root == null){
            return;
        }
        if (level == res.size()){
            res.add(root.val);
        }
        preRightOrder(root.right,res,level+1);
        preRightOrder(root.left,res,level+1);
    }

// 计算满二叉树节点的个数

   private int countLevel(TreeNode root){
        int level = 0;
        while(root != null){
            level++;
            root = root.left;
        }
        return level;
    }

    // 统计使用分治的方法
    public int countNodes(TreeNode root){
        if (root == null){
            return 0;
        }
        int left = countLevel(root.left);
        int right = countLevel(root.right);
        if (left == right){
            return countNodes(root.right) + (1<<left);
        }else {
            return countNodes(root.left) + (1<<right);
        }
    }
    

使用的是 满二叉树的计算公式
// 使用一遍遍历进行计算

 public int countNodes(TreeNode root){
        if (root == null){
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

// 使用递归直接反转为二叉树

// 反转二叉树直接使用后序遍历
    public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return root;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

// 使用迭代反转二叉树

 // 使用迭代反转二叉树
    public TreeNode invertTree2(TreeNode root) {
        if (root == null){
            return null;
        }
        // 使用队列是应为以及反转的加入节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }
        }
        return root;
    }

// 返回二茬搜索树的第k小
// 直接使用二叉树中序的非递归进行遍历

  public int kthSmallest(TreeNode root, int k) {
         Stack<TreeNode> stack = new Stack<>();
         TreeNode cur = root;
         while (!stack.empty() || cur != null){
             if (cur != null){
                 stack.push(cur);
                 cur = cur.left;
             }else {
                 cur = stack.pop();
                 if (--k == 0){
                     return cur.val;
                 }
                 // 这里不要进行判null 否则无法进入cur == null方法体中
                 cur = cur.right;
             }
         }
         return -1;
    }

// 二叉树最近公共祖先

后序遍历

1. 为null 直接返回null
2. 遍历左右节点
3. 如果root 节点等于p或者q ,直接返回root
4. 如果left不为null, 右不为null 说明两个节点分布两边返回root
5. 如果只有左为null 或者right为空 ,返回不为空的节点
6. 否则返回null;

 // 二茬树最近公共祖先
    // 分治的思想
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         if (root == null){
             return null;
         }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (root.val == p.val || root.val == q.val){
            return root;
        }
        if (left != null && right != null){
            return root;
        }
        if (left != null){
            return left;
        }
        if (right != null){
            return right;
        }
        return null;
    }

// 计算二叉树的所有路径
// 这里使用一个栈保存每一步的中间结果

  public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<String> str_stack = new Stack<>();
        stack.push(root);
        str_stack.push(root.val + "");
        String path = "";
        while (!stack.empty()){
            TreeNode node = stack.pop();
            path = str_stack.pop();
            if (node.left == null && node.right == null){
                result.add(path);
            }
            if (node.right != null){
                stack.push(root.right);
                str_stack.push(path + "->"+node.right.val);
            }
            if (node.left != null){
                stack.push(root.left);
                str_stack.push(path +"->"+node.left.val);
            }
        }
        return result;
    }

// 递归遍历二叉树

 // 递归遍历二叉树所有路径
    public List<String> binaryTreePaths2(TreeNode root) {
        List<String> paths = new LinkedList<>();
        construct_paths(root,"",paths);
        return paths;
    }

    private void construct_paths(TreeNode root, String path, List<String> paths) {
        if (root != null){
            path += Integer.toString(root.val);
            if (root.left == null && root.right == null){
                paths.add(path);
            }else {
                path += "->";
                construct_paths(root.left,path,paths);
                construct_paths(root.right,path,paths);
            }
        }
    }

// 二叉树的序列化和反序列化

1. 使用二叉树的前序遍历进行封装,主要为null的直接设置为"#"等符号
2. 使用链表进行解析
3. 如果头结点为"#",解析为null,否则创建新节点root
4. 并迭代解析 root的左,root的右节点

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return reSerialize(root,"");
    }

    private String reSerialize(TreeNode root, String str) {
        if (root == null){
            str += "#"+" ";
        }else {
            str += root.val + " ";
            str = reSerialize(root.left,str);
            str = reSerialize(root.right,str);
        }
        return str;
    }
    
     public String serialize(TreeNode root) {
        if (root == null){
            return "# ";
        }
        String str = "";
        // 如果不传参 ,就想象为一个三个节点的树,中间建立遍历 ,使用相加模式
        // 传参则使用,= 直接赋值因为参数已经随其变化
        str += root.val + " ";
        str += serialize(root.left);
        str += serialize(root.right);
        return str;
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String originData = data.trim();
        String[] res = originData.split(" ");
        List<String> data_list = new LinkedList<String>(Arrays.asList(res));
        return reDeserialize(data_list);
    }

    private TreeNode reDeserialize(List<String> data_list) {
        if (data_list.get(0).equals("#")){
            data_list.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(data_list.get(0)));
        data_list.remove(0);
        root.left = reDeserialize(data_list);
        root.right = reDeserialize(data_list);
        return root;
    }
}

// 使用层次遍历序列号和解序列号树
使用层次遍历主要是保留null节点用#代替
而在解析是如果当前为null则不会加入队列也就不会进行迭代的解析
只有非空的才加入队列进行迭代解析

 // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "" || data.length() == 0){
            return null;
        }
        String originData = data.trim();
        String[] res = originData.split(" ");
        List<String> data_list = new LinkedList<String>(Arrays.asList(res));
        return reDeserialize(data_list);
    }

    private TreeNode reDeserialize(List<String> data_list) {
        TreeNode root = new TreeNode(Integer.parseInt(data_list.get(0)));
        data_list.remove(0);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (data_list.get(0).equals("#")){
                node.left = null;
            }else {
                node.left = new TreeNode(Integer.parseInt(data_list.get(0)));
                queue.offer(node.left);
            }
            data_list.remove(0);
            if (data_list.get(0).equals("#")){
                node.right = null;
            }else {
                node.right = new TreeNode(Integer.parseInt(data_list.get(0)));
                queue.offer(node.right);
            }
            data_list.remove(0);
        }
        return root;
    }
 // 层次遍历序列化
    public String serialize(TreeNode root) {
        if (root == null){
            return "";
        }
        String res = "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node == null){
                res += "# ";
            }else {
                res += node.val + " ";
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return res;
    }
    ```
// 打家劫舍
状态转移方程的找到

p[root] = Max(dp[l]+dp[r], root.val+dp[ll]+dp[lr]+dp[rr]+dp[rl], dp[l]+dp[rl]+dp[rr], dp[r]+dp[lr]+dp[rl])

dp[root] = Max(dp[l]+dp[r], root.val+dp[ll]+dp[lr]+dp[rr]+dp[rl]);

public int rob(TreeNode root) {
return Solution(root).val;
}

public TreeNode Solution(TreeNode root){
    if(root == null){
        TreeNode newNode = new TreeNode(0);
        return Solution(newNode);
    }
    if(root.left == null && root.right == null){
        root.left = new TreeNode(0);
        root.right = new TreeNode(0);
        return root;
    }

    root.left = Solution(root.left);
    root.right = Solution(root.right);
    root.val = Math.max(root.left.val + root.right.val, root.val + root.left.left.val + root.left.right.val + root.right.left.val + root.right.right.val);

    return root;
}

// 左叶子节点之和
// 使用先序遍历的原因是,根节点的遍历顺序在子节点的遍历顺序之前
这样记录先序遍历的前驱节点来判断是否,当前节点是否是左节点

 public int sumOfLeftLeaves(TreeNode root) {
        if (root == null){
            return 0;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode pre = null;
        int sum = 0;
        while (!stack.empty()){
            TreeNode node = stack.pop();
            if (node.left == null && node.right == null){
                if (pre != null && pre.left != null && pre.left.val == node.val){
                    sum += node.val;
                }
            }
            pre = node;
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return sum;
    }

// 使用迭代的方式遍历所有的左叶子节点

  int res = 0;
    public int sumOfLeftLeaves2(TreeNode root) {
        if (root == null){
            return 0;
        }
        preOrder(root,null);
        return res;
    }

    private void preOrder(TreeNode root, TreeNode pre) {
        if (root == null){
            return;
        }
        if (root.left == null && root.right == null){
            if (pre != null && pre.left != null && pre.left.val == root.val){
                res += root.val;
            }
        }
        preOrder(root.left,root);
        preOrder(root.right,root);
    }
    

// 也可以直接判断root.left是不是叶子,是的化加上

 public int sumOfLeftLeaves(TreeNode root) {
        if (root == null){
            return 0;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode pre = null;
        int sum = 0;
        while (!stack.empty()){
            TreeNode node = stack.pop();
            if (node.left != null){
                if (node.left.left == null && node.left.right == null){
                    sum += node.left.val;
                }
            }
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return sum;
    }

// 删除二叉树中的节点

 // 删除节点三种情况: 1. 左节点为null 2. 右节点为null 3. 左右都不null
 1. 如果左节点为null, 交换右节点将右节点赋值为null,(这里隐含左右都为null,实际上直接赋值为null, 也就是将右的null交换)
 2. 如果右节点为null,交换左节点,并将根的左节点赋值为null
 3. 如果左右都不为null,找前驱代替当前节点,当前的右指向前驱的右孩子
 4. 前驱的左孩子
    public TreeNode deleteNode2(TreeNode root,int key){
        if (root == null){
            return null;
        }
        if (root.val > key){
            TreeNode left = deleteNode(root.left, key);
            return left;
        }
        if (root.val < key){
            TreeNode right = deleteNode(root.right, key);
            return right;
        }

        if (root.val == key){
            if (root.left == null){
                TreeNode right = root.right;
                root.right = null;
                return right;
            }

            if (root.right == null){
                TreeNode left = root.left;
                root.left = null;
                return left;
            }
            TreeNode pre = findPre(root.left);
            TreeNode preCopy = new TreeNode(pre.val);
            preCopy.left = removeRight(root.left);
            preCopy.right = root.right;
            root.left = null;
            root.right = null;
            return preCopy;
        }
        return root;
    }

    private TreeNode removeRight(TreeNode root) {
        if (root.right == null){
            TreeNode left = root.left;
            root.left = null;
            return left;
        }
        while(root.right != null)
        return root;
    }

    private TreeNode findPre(TreeNode root) {
        while (root.right != null){
            root = root.right;
        }
        return root;
    }

// 出现次数最多的子树元素之和
//

 HashMap<Integer,Integer> map = new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        int sum = findRoot(root);
        List<Integer> list = new ArrayList<>();
        Set<Map.Entry<Integer, Integer>> e = map.entrySet();
        int max = 0;
        for (Map.Entry<Integer, Integer> entity :e) {
            if (entity.getValue()  > max){
                max = entity.getValue();
            }
        }
        for (Map.Entry<Integer, Integer> entity :e) {
            if (entity.getValue() == max){
                list.add(entity.getKey());
            }
        }
        int[] a = new int[list.size()];
        for (int i=0;i<list.size();i++){
            a[i] = list.get(i);
        }
        return a;
    }

    private int findRoot(TreeNode root) {
        if (root == null){
            return 0;
        }
        int sum = 0;
        sum += findRoot(root.left);
        sum += findRoot(root.right);
        sum += root.val;
        map.put(sum,map.getOrDefault(sum,0)+1);
        return sum;
    }

 HashMap<Integer,Integer> map = new HashMap<>();
    public int[] findFrequentTreeSum(TreeNode root) {
        int max= 0;
        int sum = findRoot(root);
        List<Integer> list = new ArrayList<>();
        // 两次for循环优化一次循环
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entity :entries) {
            if (entity.getValue() > max){
                max = entity.getValue();
                list.clear();
                list.add(entity.getKey());
            }else if (entity.getValue() == max){
                list.add(entity.getKey());
            }
        }
        int[] a = new int[list.size()];
        for (int i=0;i<list.size();i++){
            a[i] = list.get(i);
        }
        return a;
    }

    private int findRoot(TreeNode root) {
        if (root == null){
            return 0;
        }
        int sum = 0;
        sum += findRoot(root.left);
        sum += findRoot(root.right);
        sum += root.val;
        map.put(sum,map.getOrDefault(sum,0)+1);
        return sum;
    }