首页 > 其他分享 >[剑指offer] 树[上]篇

[剑指offer] 树[上]篇

时间:2023-09-21 22:46:39浏览次数:30  
标签:right return offer int null root public

JZ55 二叉树的深度

 1 /* 递归 */
 2 public class JZ55_1
 3 {
 4     public static int TreeDepth(TreeNode root)
 5     {
 6         if (root == null) return 0;
 7         return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
 8     }
 9 }
10 
11 /* 层次遍历 */
12 public class JZ55_2
13 {
14     public static int TreeDepth(TreeNode root)
15     {
16         if (root == null) return 0;
17         Queue<TreeNode> queue = new LinkedList<>();
18         int size = -1, res = 0;
19         queue.add(root);
20         while (!queue.isEmpty())
21         {
22             size = queue.size();
23             while (size != 0)
24             {
25                 TreeNode poll = queue.poll();
26                 if (poll.left != null)
27                     queue.add(poll.left);
28                 if (poll.right != null)
29                     queue.add(poll.right);
30                 size--;
31             }
32             res++;
33         }
34         return res;
35     }
36 }

JZ77 按之字形顺序打印二叉树

 1 /* 模拟 */
 2 public class JZ77_1
 3 {
 4     public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
 5     {
 6         ArrayList<ArrayList<Integer>> res = new ArrayList<>();
 7         if (pRoot == null) return res;
 8         Queue<TreeNode> queue = new LinkedList<>();
 9         boolean revFlag = false;
10         queue.add(pRoot);
11         while (!queue.isEmpty())
12         {
13             ArrayList<Integer> temp = new ArrayList<>();
14             int size = queue.size();
15             while (size != 0)
16             {
17                 TreeNode poll = queue.poll();
18                 temp.add(poll.val);
19                 if (poll.left != null)
20                     queue.add(poll.left);
21                 if (poll.right != null)
22                     queue.add(poll.right);
23                 size--;
24             }
25             if (revFlag)
26                 Collections.reverse(temp);
27             res.add(temp);
28             revFlag = !revFlag;
29         }
30         return res;
31     }
32 }
33 
34 /* 双栈法 */
35 public class JZ77_2
36 {
37     public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot)
38     {
39         ArrayList<ArrayList<Integer>> res = new ArrayList<>();
40         Stack<TreeNode> stack1 = new Stack<>();
41         Stack<TreeNode> stack2 = new Stack<>();
42         if (pRoot != null)
43             stack1.push(pRoot);
44         while (!stack1.isEmpty() || !stack2.isEmpty())
45         {
46             ArrayList<Integer> temp = new ArrayList<>();
47             if (!stack1.isEmpty())
48             {
49                 while (!stack1.isEmpty())
50                 {
51                     TreeNode popNode = stack1.pop();
52                     temp.add(popNode.val);
53                     if (popNode.left != null)
54                         stack2.push(popNode.left);
55                     if (popNode.right != null)
56                         stack2.push(popNode.right);
57                 }
58             }
59             else
60             {
61                 while (!stack2.isEmpty())
62                 {
63                     TreeNode popNode = stack2.pop();
64                     temp.add(popNode.val);
65                     if (popNode.right != null)
66                         stack1.push(popNode.right);
67                     if (popNode.left != null)
68                         stack1.push(popNode.left);
69                 }
70             }
71             res.add(temp);
72         }
73         return res;
74     }
75 }

JZ54 二叉搜索树的第k个节点

 1 /* 递归 */
 2 public class JZ54_1
 3 {
 4     public static int num;
 5 
 6     public static int KthNode(TreeNode proot, int k)
 7     {
 8         num = k;
 9         return inorder(proot);
10     }
11 
12     private static int inorder(TreeNode proot)
13     {
14         if (proot != null)
15         {
16             int left = inorder(proot.left);
17             if (left != -1)
18                 return left;
19             if (num == 1)
20                 return proot.val;
21             num--;
22             return inorder(proot.right);
23         }
24         return -1;
25     }
26 }
27 
28 /* 非递归 */
29 public class JZ54_2
30 {
31     public static int KthNode(TreeNode proot, int k)
32     {
33         Stack<TreeNode> stack = new Stack<>();
34         while (!stack.isEmpty() || proot != null)
35         {
36             if (proot != null)
37             {
38                 stack.push(proot);
39                 proot = proot.left;
40             }
41             else
42             {
43                 TreeNode popNode = stack.pop();
44                 if (k == 1) return popNode.val;
45                 k--;
46                 proot = popNode.right;
47             }
48         }
49         return -1;
50     }
51 }

JZ7 重建二叉树

 1 /* 递归 */
 2 public class JZ7_1
 3 {
 4     public static TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder)
 5     {
 6         return struct(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1);
 7     }
 8 
 9     public static TreeNode struct(int[] preOrder, int preS, int preE, int[] vinOrder, int vinS, int vinE)
10     {
11         if (preS > preE || vinS > vinE) return null;
12         TreeNode root = new TreeNode(preOrder[preS]);
13         int pivot = vinS;
14         while (vinOrder[pivot] != preOrder[preS])
15             pivot++;
16         int len = pivot - vinS;
17         root.left = struct(preOrder, preS + 1, preS + len, vinOrder, vinS, pivot - 1);
18         root.right = struct(preOrder, preS + len + 1, preE, vinOrder, pivot + 1, vinE);
19         return root;
20     }
21 }

JZ26 树的子结构⭐

 1 /* 递归 */
 2 public class JZ26_1
 3 {
 4     public static boolean HasSubtree(TreeNode root1, TreeNode root2)
 5     {
 6         if (root2 == null) return false;
 7         else return fun(root1, root2);
 8     }
 9 
10     public static boolean fun(TreeNode root1, TreeNode root2)
11     {
12         if (root2 == null) return true;
13         if (root1 == null) return false;
14         boolean one = (root1.val == root2.val) && fun(root1.left, root2.left) && fun(root1.right, root2.right);
15         if (one) return true;
16         boolean two = fun(root1.left, root2) || fun(root1.right, root2);
17         return two;
18     }
19 }
20 
21 /* 递归版本2 */
22 public class JZ26_2
23 {
24     public static boolean HasSubtree(TreeNode root1, TreeNode root2)
25     {
26         boolean res = false;
27         if (root1 != null && root2 != null)
28         {
29             if (root1.val == root2.val)
30                 res = judge(root1, root2);
31             if (!res)
32                 res = HasSubtree(root1.left, root2);
33             if (!res)
34                 res = HasSubtree(root1.right, root2);
35         }
36         return res;
37     }
38 
39     public static boolean judge(TreeNode root1, TreeNode root2)
40     {
41         if (root2 == null) return true;
42         if (root1 == null) return false;
43         if (root1.val != root2.val) return false;
44         return judge(root1.left, root2.left) && judge(root1.right, root2.right);
45     }
46 }

JZ27 二叉树的镜像

 1 /* 递归 */
 2 public class JZ7_1
 3 {
 4     public static TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder)
 5     {
 6         return struct(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1);
 7     }
 8 
 9     public static TreeNode struct(int[] preOrder, int preS, int preE, int[] vinOrder, int vinS, int vinE)
10     {
11         if (preS > preE || vinS > vinE) return null;
12         TreeNode root = new TreeNode(preOrder[preS]);
13         int pivot = vinS;
14         while (vinOrder[pivot] != preOrder[preS])
15             pivot++;
16         int len = pivot - vinS;
17         root.left = struct(preOrder, preS + 1, preS + len, vinOrder, vinS, pivot - 1);
18         root.right = struct(preOrder, preS + len + 1, preE, vinOrder, pivot + 1, vinE);
19         return root;
20     }
21 }

JZ32 从上往下打印二叉树

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

JZ33 二叉搜索树的后序遍历序列

 1 /* 递归 */
 2 public class JZ33_1
 3 {
 4     public static boolean VerifySquenceOfBST(int[] sequence)
 5     {
 6         if (sequence.length == 0) return false;
 7         return judge(sequence, 0, sequence.length - 1);
 8     }
 9 
10     public static boolean judge(int[] sequence, int left, int right)
11     {
12         if (left >= right) return true;
13         int idx = left;
14         while (sequence[idx] < sequence[right] && idx < right)
15             idx++;
16         for (int i = idx; i < right; i++)
17         {
18             if (sequence[i] < sequence[right])
19                 return false;
20         }
21         return judge(sequence, left, idx - 1) && judge(sequence, idx, right - 1);
22     }
23 }
24 
25 /* ⭐若将中序序列当作入栈序列,那么后序序列应该是合法的出栈序列⭐ */
26 public class JZ33_2
27 {
28     public static boolean VerifySquenceOfBST(int[] sequence)
29     {
30         if (sequence.length == 0) return false;
31         int j = 0;
32         ArrayList<Integer> inOrder = new ArrayList<>();
33         Stack<Integer> stack = new Stack<>();
34         for (int num : sequence) inOrder.add(num);
35         Collections.sort(inOrder);
36         for (int num : inOrder)
37         {
38             stack.add(num);
39             while (!stack.isEmpty() && stack.peek() == sequence[j])
40             {
41                 stack.pop();
42                 j++;
43             }
44         }
45         return j == sequence.length;
46     }
47 }

JZ82 二叉树中和为某一值的路径(一)

 1 /* 递归 */
 2 public class JZ82_1
 3 {
 4     public static boolean hasPathSum(TreeNode root, int sum)
 5     {
 6         if (root == null)
 7             return false;
 8         if (root.left == null && root.right == null && sum - root.val == 0)
 9             return true;
10         return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
11     }
12 }
13 
14 /* 层次 */
15 public class JZ82_2
16 {
17     public static boolean hasPathSum(TreeNode root, int sum)
18     {
19         if (root == null) return false;
20         Queue<TreeNode> queue = new LinkedList<>();
21         queue.add(root);
22         while (!queue.isEmpty())
23         {
24             TreeNode pollNode = queue.poll();
25             if (pollNode.left != null)
26             {
27                 pollNode.left.val += pollNode.val;
28                 queue.add(pollNode.left);
29 
30             }
31             if (pollNode.right != null)
32             {
33                 pollNode.right.val += pollNode.val;
34                 queue.add(pollNode.right);
35             }
36             if (pollNode.val == sum && pollNode.left == null && pollNode.right == null)
37                 return true;
38         }
39         return false;
40     }
41 }

JZ34 二叉树中和为某一值的路径(二)

 1 /* DFS */
 2 public class JZ34_1
 3 {
 4     public static ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
 5 
 6     public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target)
 7     {
 8         if (root == null) return res;
 9         dfs(root, target, new ArrayList<Integer>());
10         return res;
11     }
12 
13     public static void dfs(TreeNode root, int target, ArrayList<Integer> path)
14     {
15         path.add(root.val);
16         target -= root.val;
17         if (root.left == null && root.right == null && target == 0)
18             res.add(new ArrayList<>(path));
19         if (root.left != null)
20             dfs(root.left, target, path);
21         if (root.right != null)
22             dfs(root.right, target, path);
23         path.remove(path.size() - 1);
24     }
25 }

标签:right,return,offer,int,null,root,public
From: https://www.cnblogs.com/VividBinGo/p/17721156.html

相关文章

  • [剑指offer] 排序篇
    JZ3 数组中重复的数字⭐1/*2*①map/set3*②因为"长度为n的数组里的所有数字都在0到n-1的范围内"4*所以对数组进行调整使得numbers[idx]==idx5**/6publicclassJZ3_17{8publicstaticintduplicate(int[]numbers)9{10f......
  • [剑指offer] 位运算篇
    JZ65 不用加减乘除做加法⭐1/*^模拟不进位相加,&模拟进位(递归)*/2publicclassJZ65_13{4publicstaticintAdd(intnum1,intnum2)5{6if(num2==0)returnnum1;7returnAdd(num1^num2,(num1&num2)<<1);8}......
  • 《剑指Offer》-21-调整数组顺序使奇数位于偶数前面
    第一想法是双指针,一个指针用于遍历,一个指针用于标记奇数和偶数的分界,而调整位置则通过交换来实现思路来自于快排代码,分隔指针+交换,也算是双指针? vector<int>exchange(vector<int>&nums){ //一个遍历指针,一个分隔指针,odd指向第一个偶数 intodd=0; for(inti=0;i......
  • 《剑指Offer》-34-二叉树中和为某一值的路径
    思路要求是从根节点开始的路径,这会比从任意节点开始的路径简单很多思路是从根节点开始遍历每一条路径,如果和没有达到目标值就继续向下遍历大于就回退,等于就返回到结果集中,可以看到这是一个回溯动作实际过程中,首先不管是等于还是大于,回退pop()操作都要执行,这样才不会影响到后......
  • 剑指Offer面试题7:重建二叉树
    一、题目给定节点数为n的二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。提示:1.vin.length== pre.length2.pre和vin 均无重复元素3.vin出现的元素均出现在 ......
  • 剑指Offer面试题6:从尾到头打印链表
    一、题目输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)如输入{1,2,3}的链表如下图:返回一个数组为[3,2,1]二、题解看到这题很多人第一反应是从头到尾输出会比较简单,于是我们很自然想到把链表中的节点指针反过来,改变链表结构就可以从头到尾输出了。但该方法......
  • 剑指Offer面试题5:替换空格
    一、题目请实现一个函数,把字符串中的每个空格替换成“%20”。例如:输入“Wearehappy.",则输出”We%20are%20happy."。二、解析2.1解法一申请一个临时数组,然后再遍历这个字符串的每个字符,如果不是空格就把遍历的字符添加到临时数组中,如果是空格就添加3个符'%','2','0'分别到临时数组......
  • [剑指offer] 队列&栈篇
    JZ9 用两个栈实现队列1/*模拟入队*/2publicclassJZ9_13{4publicstaticStack<Integer>stack1=newStack<Integer>();5publicstaticStack<Integer>stack2=newStack<Integer>();67publicstaticvoidpush(intnod......
  • [剑指offer] 回溯篇
    JZ12矩阵中的路径1/*DFS*/2publicclassJZ12_13{4publicstaticboolean[][]vis;5publicstaticint[]dx=newint[]{-1,1,0,0};6publicstaticint[]dy=newint[]{0,0,-1,1};78publicstaticbooleanhasPath(char[][]......
  • [剑指offer] 模拟篇
    JZ29 顺时针打印矩阵1/*模拟*/2publicclassJZ29_13{4publicstaticArrayList<Integer>printMatrix(int[][]matrix)5{6ArrayList<Integer>res=newArrayList<>();7intleft=0,right=matrix[0].length-......