[剑指offer] 树[下]篇

JZ36 二叉搜索树与双向链表⭐

 1 /* 中序递归 */
 2 public class JZ36_1
 3 {
 4     public static TreeNode Convert(TreeNode pRootOfTree)
 5     {
 6         inOrder(pRootOfTree);
 7         TreeNode res = pRootOfTree;
 8         while (res != null && res.left != null)
 9             res = res.left;
10         return res;
11     }
12 
13     private static TreeNode inOrder(TreeNode root)
14     {
15         if (root == null) return null;
16         if (root.left == null && root.right == null) return root;
17         TreeNode leftPoint = null, rightPoint = null;
18         if (root.left != null)
19         {
20             leftPoint = inOrder(root.left);
21             while (leftPoint.right != null)
22                 leftPoint = leftPoint.right;
23             leftPoint.right = root;
24             root.left = leftPoint;
25         }
26         if (root.right != null)
27         {
28             rightPoint = inOrder(root.right);
29             rightPoint.left = root;
30             root.right = rightPoint;
31         }
32         return leftPoint != null ? leftPoint : root;
33     }
34 }
35 
36 /* 中序非递归 */
37 public class JZ36_2
38 {
39     public static TreeNode Convert(TreeNode pRootOfTree)
40     {
41         Stack<TreeNode> stack = new Stack<>();
42         TreeNode head = null, tail = null;
43         while (pRootOfTree != null || !stack.isEmpty())
44         {
45             while (pRootOfTree != null)
46             {
47                 stack.push(pRootOfTree);
48                 pRootOfTree = pRootOfTree.left;
49             }
50             TreeNode popNode = stack.pop();
51             if (head == null)
52             {
53                 head = tail = popNode;
54             }
55             else
56             {
57                 popNode.left = tail;
58                 tail.right = popNode;
59                 tail = popNode;
60             }
61             pRootOfTree = popNode.right;
62         }
63         return head;
64     }
65 }

JZ79 判断是不是平衡二叉树

 1 /* 从下到上递归 */
 2 public class JZ79_1
 3 {
 4     public static boolean IsBalanced_Solution(TreeNode pRoot)
 5     {
 6         return judge(pRoot) != -1;
 7     }
 8 
 9     public static int judge(TreeNode pRoot)
10     {
11         if (pRoot == null) return 0;
12         if (pRoot.left == null && pRoot.right == null) return 1;
13         int leftHigh = judge(pRoot.left);
14         int rightHigh = judge(pRoot.right);
15         if (leftHigh == -1 || rightHigh == -1) return -1;
16         if (Math.abs(leftHigh - rightHigh) > 1) return -1;
17         return Math.max(leftHigh, rightHigh) + 1;
18     }
19 }
20 
21 /* 从上到下递归 */
22 public class JZ79_2
23 {
24     public static boolean IsBalanced_Solution(TreeNode pRoot)
25     {
26         if (pRoot == null) return true;
27         int l = calHeight(pRoot.left);
28         int r = calHeight(pRoot.right);
29         if (Math.abs(l - r) > 1) return false;
30         else return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
31     }
32 
33     public static int calHeight(TreeNode pRoot)
34     {
35         if (pRoot == null) return 0;
36         if (pRoot.left == null && pRoot.right == null) return 1;
37         return Math.max(calHeight(pRoot.left), calHeight(pRoot.right)) + 1;
38     }
39 }

JZ8 二叉树的下一个结点

 1 /*
 2  * (1)若结点有右子树，则下一个结点是其右子树中最左边的结点
 3  * (2)若结点没有右子树，并且是父节点的左结点，则下一个结点就是他的父节点
 4  * (3)若结点没有右子树，并且是父节点的右结点，则应该沿着父节点向上，直到找到的结点是一个左结点。则下一个结点是该左结点的父节点
 5  * */
 6 public class JZ8_1
 7 {
 8     public static TreeLinkNode GetNext(TreeLinkNode pNode)
 9     {
10         if (pNode.right != null)
11         {
12             pNode = pNode.right;
13             while (pNode.left != null)
14                 pNode = pNode.left;
15             return pNode;
16         }
17         else
18         {
19             if (pNode.next == null) return null;
20             if (pNode.next.left == pNode)
21                 return pNode.next;
22             else
23             {
24                 while (pNode.next != null && pNode.next.left != pNode)
25                     pNode = pNode.next;
26                 return pNode.next;
27             }
28         }
29     }
30 }

JZ28 对称的二叉树

 1 /* 递归 */
 2 public class JZ28_1
 3 {
 4     public static boolean isSymmetrical(TreeNode pRoot)
 5     {
 6         return judge(pRoot, pRoot);
 7     }
 8 
 9     public static boolean judge(TreeNode leftNode, TreeNode rightNode)
10     {
11         if (leftNode == null && rightNode == null) return true;
12         if (leftNode == null || rightNode == null) return false;
13         if (leftNode.val != rightNode.val) return false;
14         return judge(leftNode.left, rightNode.right) && judge(leftNode.right, rightNode.left);
15     }
16 }
17 
18 /* 队列 */
19 public class JZ28_2
20 {
21     public static boolean isSymmetrical(TreeNode pRoot)
22     {
23         Queue<TreeNode> queue = new LinkedList<>();
24         queue.add(pRoot);
25         queue.add(pRoot);
26         while (!queue.isEmpty())
27         {
28             TreeNode leftNode = queue.poll();
29             TreeNode rightNode = queue.poll();
30             if ((leftNode != null && rightNode == null) || (leftNode == null && rightNode != null))
31                 return false;
32             if (leftNode == null && rightNode == null) continue;
33             if (leftNode.val != rightNode.val) return false;
34             queue.add(leftNode.left);
35             queue.add(rightNode.right);
36             queue.add(leftNode.right);
37             queue.add(rightNode.left);
38         }
39         return true;
40     }
41 }

JZ78 把二叉树打印成多行

 1 /* 层次遍历(与JZ32类似) */
 2 public class JZ78_1
 3 {
 4     public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
 5     {
 6         ArrayList<ArrayList<Integer>> res = new ArrayList<>();
 7         Queue<TreeNode> queue = new LinkedList<>();
 8         if (pRoot == null) return res;
 9         queue.add(pRoot);
10         while (!queue.isEmpty())
11         {
12             int size = queue.size();
13             ArrayList<Integer> temp = new ArrayList<>();
14             while (size > 0)
15             {
16                 TreeNode poll = queue.poll();
17                 temp.add(poll.val);
18                 if (poll.left != null)
19                     queue.add(poll.left);
20                 if (poll.right != null)
21                     queue.add(poll.right);
22                 size--;
23             }
24             res.add(new ArrayList<>(temp));
25         }
26         return res;
27     }
28 }
29 
30 /* 递归层次遍历(与JZ32类似) */
31 public class JZ78_2
32 {
33     public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
34     {
35         ArrayList<ArrayList<Integer>> res = new ArrayList<>();
36         levelTravel(pRoot, res, 1);
37         return res;
38     }
39 
40     public static void levelTravel(TreeNode root, ArrayList<ArrayList<Integer>> temp, int depth)
41     {
42         if (root == null) return;
43         if (temp.size() < depth)
44         {
45             ArrayList<Integer> addList = new ArrayList<>();
46             addList.add(root.val);
47             temp.add(addList);
48         }
49         else
50         {
51             temp.get(depth - 1).add(root.val);
52         }
53         levelTravel(root.left, temp, depth + 1);
54         levelTravel(root.right, temp, depth + 1);
55     }
56 }

JZ37 序列化二叉树⭐

 1 /* 先序 */
 2 public class JZ37_1
 3 {
 4     public static int idx;
 5 
 6     public static String Serialize(TreeNode root)
 7     {
 8         if (root == null) return "#,";
 9         String res = "";
10         res += root.val + ",";
11         return res + Serialize(root.left) + Serialize(root.right);
12     }
13 
14     public static TreeNode Deserialize(String str)
15     {
16         idx = 0;
17         return Deserialize(str.split(","));
18     }
19 
20     public static TreeNode Deserialize(String[] strArr)
21     {
22         if (idx >= strArr.length) return null;
23         if (strArr[idx].equals("#"))
24         {
25             idx++;
26             return null;
27         }
28 
29         TreeNode root = new TreeNode(Integer.parseInt(strArr[idx++]));
30         root.left = Deserialize(strArr);
31         root.right = Deserialize(strArr);
32         return root;
33     }
34 }

JZ84 二叉树中和为某一值的路径(三)⭐

 1 /* 递归版本1 */
 2 public class JZ84_1
 3 {
 4     public static int res = 0;
 5 
 6     public static int FindPath(TreeNode root, int sum)
 7     {
 8         dfs(root, sum, false);
 9         return res;
10     }
11 
12     public static void dfs(TreeNode root, int sum, boolean flag)
13     {
14         if (root == null) return ;
15         if (!flag)
16         {
17             dfs(root.left, sum, false);
18             dfs(root.right, sum, false);
19         }
20         if (sum - root.val == 0) res++;
21         dfs(root.left, sum - root.val, true);
22         dfs(root.right, sum - root.val, true);
23     }
24 }
25 
26 /* 递归版本2 */
27 public class JZ84_2
28 {
29     public static int res = 0;
30 
31     public static int FindPath(TreeNode root, int sum)
32     {
33         if (root == null) return 0;
34         dfs(root, sum);
35         FindPath(root.left, sum);
36         FindPath(root.right, sum);
37         return res;
38     }
39 
40     public static void dfs(TreeNode root, int sum)
41     {
42         if (root == null) return;
43         sum -= root.val;
44         if (sum == 0) res++;
45         dfs(root.left, sum );
46         dfs(root.right, sum);
47     }
48 }
49 
50 /* ⭐hash+dfs⭐ */
51 public class JZ84_3
52 {
53     public static int res = 0;
54     public static HashMap<Integer, Integer> map = new HashMap<>();
55 
56     public static int FindPath(TreeNode root, int sum)
57     {
58         map.put(0, 1);
59         return dfs(root, sum, 0);
60     }
61 
62     public static int dfs(TreeNode root, int sum, int val)
63     {
64         if (root == null) return 0;
65         val += root.val;
66         res += map.getOrDefault(val - sum, 0);
67         map.put(val, map.getOrDefault(val, 0) + 1);
68         dfs(root.left, sum, val);
69         dfs(root.right, sum, val);
70         map.put(val, map.get(val) - 1);
71         return res;
72     }
73 }

JZ86 在二叉树中找到两个节点的最近公共祖先⭐

  1 /*⭐递归⭐*/
  2 public class JZ86_1
  3 {
  4     public static int lowestCommonAncestor(TreeNode root, int o1, int o2)
  5     {
  6         return find(root, o1, o2).val;
  7     }
  8 
  9     private static TreeNode find(TreeNode root, int o1, int o2)
 10     {
 11         if (root == null || root.val == o1 || root.val == o2)
 12             return root;
 13         TreeNode left = find(root.left, o1, o2);
 14         TreeNode right = find(root.right, o1, o2);
 15         if (left != null && right != null) return root;
 16         else return left == null ? right : left;
 17     }
 18 }
 19 
 20 /* 层次 */
 21 public class JZ86_2
 22 {
 23     public static int lowestCommonAncestor(TreeNode root, int o1, int o2)
 24     {
 25         Queue<TreeNode> queue = new LinkedList<>();
 26         HashMap<Integer, Integer> map = new HashMap<>();
 27         ArrayList<Integer> temp = new ArrayList<>();
 28         map.put(root.val, Integer.MAX_VALUE);
 29         queue.add(root);
 30         while (!map.containsKey(o1) || !map.containsKey(o2))
 31         {
 32             TreeNode treeNode = queue.poll();
 33             if (treeNode.left != null)
 34             {
 35                 queue.add(treeNode.left);
 36                 map.put(treeNode.left.val, treeNode.val);
 37             }
 38             if (treeNode.right != null)
 39             {
 40                 queue.add(treeNode.right);
 41                 map.put(treeNode.right.val, treeNode.val);
 42             }
 43         }
 44         while (o1 != Integer.MAX_VALUE)
 45         {
 46             temp.add(o1);
 47             o1 = map.get(o1);
 48         }
 49         while (!temp.contains(o2))
 50         {
 51             o2 = map.get(o2);
 52         }
 53         return o2;
 54     }
 55 }
 56 
 57 /* tarjan并查集 */
 58 public class JZ86_3
 59 {
 60     public static int[] parent;
 61 
 62     public static int lowestCommonAncestor(TreeNode root, int o1, int o2)
 63     {
 64         parent = new int[100005];
 65         Arrays.fill(parent, -1);
 66         return dfs(root, o1, o2);
 67     }
 68 
 69     private static int dfs(TreeNode root, int o1, int o2)
 70     {
 71         if (root == null) return -1;
 72         int left = -1, right = -1;
 73         if (root.left != null)
 74         {
 75             left = dfs(root.left, o1, o2);
 76             merge(root.val, root.left.val);
 77         }
 78         if (root.right != null)
 79         {
 80             right = dfs(root.right, o1, o2);
 81             merge(root.val, root.right.val);
 82         }
 83         if (left == -1 && right == -1)
 84         {
 85             if (find(o1) == find(o2) && find(o1) != -1)
 86                 return find(o1);
 87             return -1;
 88         }
 89         return left == -1 ? right : left;
 90     }
 91 
 92     public static void merge(int o1, int o2)
 93     {
 94         int p1 = find(o1);
 95         int p2 = find(o2);
 96         parent[p2] = p1;
 97     }
 98 
 99     public static int find(int o1)
100     {
101         if (parent[o1] != -1)
102             return parent[o1] = find(parent[o1]);
103         return o1;
104     }
105 }

JZ68 二叉搜索树的最近公共祖先

 1 /* 非递归 */
 2 public class JZ68_1
 3 {
 4     public int lowestCommonAncestor(TreeNode root, int p, int q)
 5     {
 6         while (true)
 7         {
 8             if (p < root.val && q < root.val) root = root.left;
 9             else if (p > root.val && q > root.val) root = root.right;
10             else return root.val;
11         }
12     }
13 }
14 
15 /* 递归 */
16 public class JZ68_2
17 {
18     public int lowestCommonAncestor(TreeNode root, int p, int q)
19     {
20         if (p < root.val && q < root.val) return lowestCommonAncestor(root.left, p, q);
21         else if (p > root.val && q > root.val) return lowestCommonAncestor(root.right, p, q);
22         else return root.val;
23     }
24 }