24、二叉树中和为某一值的路径
public class Solution { private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>(); private ArrayList<Integer> list = new ArrayList<Integer>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { if(root == null) return listAll; list.add(root.val); target -= root.val; if(target == 0 && root.left == null && root.right == null) listAll.add(new ArrayList<Integer>(list)); FindPath(root.left, target); FindPath(root.right, target); list.remove(list.size()-1); return listAll; } }
38、二叉树的深度
递归遍历
public class Solution { public int TreeDepth(TreeNode root) { if(root==null){ return 0; } int left=TreeDepth(root.left)+1; int right=TreeDepth(root.right)+1; return left>right?left:right; } }
非递归遍历
import java.util.Queue; import java.util.LinkedList; public class Solution { public int TreeDepth(TreeNode pRoot) { if(pRoot == null){ return 0; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(pRoot); int depth = 0, count = 0, nextCount = 1; while(queue.size()!=0){ TreeNode top = queue.poll(); count++; if(top.left != null){ queue.add(top.left); } if(top.right != null){ queue.add(top.right); } if(count == nextCount){ nextCount = queue.size(); count = 0; depth++; } } return depth; } }
39、平衡二叉树
从根节点开始，先判断左右子树的高度差是否超过1，然后接着判断左右子树是否是平衡二叉树。这边用到了递归思想。
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if(root==null){ return true; } return IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right)&&Math.abs(getDepth(root.left)-getDepth(root.right))<=1; } public int getDepth(TreeNode node){ if(node==null){ return 0; } int left=getDepth(node.left)+1; int right=getDepth(node.right)+1; return left>right?left:right; } }
这种做法有很明显的问题，在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { return getDepth(root) != -1; } private int getDepth(TreeNode root) { if (root == null) return 0; int left = getDepth(root.left); if (left == -1) return -1; int right = getDepth(root.right); if (right == -1) return -1; return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right); } }
57、二叉树的下一个节点
思路：首先知道中序遍历的规则是：左根右，然后作图
结合图，我们可发现分成两大类：1、有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） 2、没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点…直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。
public class Solution { TreeLinkNode GetNext(TreeLinkNode node) { if(node==null) return null; if(node.right!=null){ //如果有右子树，则找右子树的最左节点 node = node.right; while(node.left!=null) node = node.left; return node; } while(node.next!=null){ //没右子树，则找第一个当前节点是父节点左孩子的节点 if(node.next.left==node) return node.next; node = node.next; } return null; //退到了根节点仍没找到，则返回null } }
