数据结构 ——二叉树总结

明天继续更

递归法：

1 二叉树展开为链表（先序遍历）

思路很容易 就是感觉有个小细节 最后从list集合拿出来的时候，拼接成新树的思路

package 二叉树;

import java.util.ArrayList;
import java.util.List;

public class 二叉树展开为链表 {
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
          this.right = right;
      }
  }

  /*
  Queue<TreeNode> queue = new ArrayDeque<>();
        preOrder(root, queue);
        while (!queue.isEmpty()){
            TreeNode curr = queue.poll();
            curr.left = null;
            curr.right = queue.peek();
        }
    }
   */
    public void flatten(TreeNode root) {
        List<TreeNode> list=new ArrayList<TreeNode>();
        dfs(root,list);
        int len=list.size();
        
        for (int i = 1; i <len ; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left=null;
            prev.right=curr;

        }



    }
    public void dfs(TreeNode root,List<TreeNode> list){
        if (root!=null){
            list.add(root);
            dfs(root.left,list);
            dfs(root.right,list);
        }

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

2 二叉树的镜像（后序遍历）

像这种交换位置的 只能是自底而上进行交互 所以一定是后序遍历 且递归的返回类型为TreeNode最好 然后直接改变自身即可。这种返回值 在null判断时 直接retrun null即可。

https://blog.csdn.net/weixin_45678130/article/details/122373131

3 路径总和（先序遍历的变形）：

感觉两个dfs的思路比较清晰 就是纯深度优先搜索的感觉
但是链接里的第二种方法中，变形在于int返回值 然后答案他不像第一种全局变量存储，而是用了个变量累加的办法 一层一层的将最终答案加回到根节点

https://blog.csdn.net/weixin_45678130/article/details/122306789

4 从叶结点开始的最小字符串（先序变形）

这个题要求从叶节点开始 也就是只能先先序 然后倒过来即可 需要一些java中字符串的操作 关键在于每一层遍历结束 要弹出一个值 因为回调了（这里比较重要）

https://blog.csdn.net/weixin_45678130/article/details/122332998

5 二叉树中的最大路径和（后序）

又是一个逐渐累加结果到根节点 而这个题是后序遍历 以前的都是固定方向的 这个没有固定 不能先序做

https://blog.csdn.net/weixin_45678130/article/details/122442676

层次遍历：

1 树的最大宽度（这题好）
https://blog.csdn.net/weixin_45678130/article/details/122399802