赞
踩
题目:530. 二叉搜索树的最小绝对差
解析:代码随想录解析
中序遍历,每次记录上一个节点pre。然后比较和记录minDiff
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { TreeNode pre = null; int minDiff = Integer.MAX_VALUE; public int getMinimumDifference(TreeNode root) { inorder(root); return minDiff; } private void inorder(TreeNode node) { if (node == null) return; inorder(node.left); if (pre != null) minDiff = Math.min(minDiff, node.val - pre.val); pre = node; inorder(node.right); } } //借助栈的中序遍历 class Solution { public int getMinimumDifference(TreeNode root) { int minDiff = Integer.MAX_VALUE; TreeNode pre = null; TreeNode cur = root; Stack<TreeNode> stack = new Stack<>(); while (cur != null || !stack.isEmpty()) { if (cur != null) { stack.push(cur); cur = cur.left; } else { cur = stack.pop(); if (pre != null) minDiff = Math.min(minDiff, cur.val - pre.val); pre = cur; cur = cur.right; } } return minDiff; } }
中序遍历
题目:501. 二叉搜索树中的众数
解析:代码随想录解析
中序遍历
/** * Definition for a binary tree node. * 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; * } * } */ class Solution { List<Integer> res = new ArrayList<>(); int maxModeCount = 0; int mode = Integer.MIN_VALUE; int modeCount = 0; public int[] findMode(TreeNode root) { //如果root为空,则返回空数组 if (root == null) return new int[0]; //否则,至少有1个众数 traversal(root); int[] array = new int[res.size()]; for (int i = 0; i < res.size(); i++) { array[i] = res.get(i); } return array; } private void traversal(TreeNode node) { if (node == null) return; traversal(node.left); //如果和当前值相同则众数的count++,否则重新记录mode,count设为1 if (node.val == mode) modeCount++; else { mode = node.val; modeCount = 1; } //因为至少有个一个数,所以肯定不会返回Integer.MIN_VALUE //若超过众数的最大值,则清空重新加入,并记录众数的最大个数 if (modeCount > maxModeCount) { maxModeCount = modeCount; res.clear(); res.add(mode); } else if (modeCount == maxModeCount) { res.add(mode); } traversal(node.right); } }
见代码注释
题目:236. 二叉树的最近公共祖先
解析:代码随想录解析
后序遍历,递归。若到null,p,q的时候返回。
然后left和right分别进行搜索,如果都为null则返回null。
如果有一边不为null,则找到p或q中的一个。
如果两边都不为null,则root为一个最小公共祖先。(如果root是最小公共祖先的祖先的话,上面的节点只有返回left或right,所以最终返回的肯定是最小公共祖先)
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p ,q); TreeNode right = lowestCommonAncestor(root.right, p ,q); if (left == null && right == null) return null; else if (left == null && right != null)//right找到一个节点 return right; else if (left != null && right == null)//left找到一个节点 return left; else//left和right都找到一个节点 return root; } }
妙啊
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。