94. Binary Tree Inorder Traversal
二叉樹(shù)的非遞歸中序遍歷
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode tmp = root;
while(tmp.left!=null){
stack.push(tmp.left);
tmp = tmp.left;
}
while(!stack.isEmpty()){
tmp = stack.pop();
res.add(tmp.val);
if(tmp.right != null){
stack.push(tmp.right);
tmp = tmp.right;
while(tmp.left!=null){
stack.push(tmp.left);
tmp = tmp.left;
}
}
}
return res;
}
}
95. Unique Binary Search Trees II
遞歸的思路方妖，對(duì)于1..n分扎，我們分別以1到n為根結(jié)點(diǎn)，然后左邊的樹(shù)構(gòu)建左子樹(shù)鲜棠，右邊的樹(shù)構(gòu)建右子樹(shù)，然后左右子樹(shù)兩兩結(jié)合培慌，這個(gè)過(guò)程可以用遞歸來(lái)完成豁陆。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n<=0)
return new ArrayList<TreeNode>();
return generateSub(1,n);
}
public List<TreeNode> generateSub(int start,int end){
List<TreeNode> res = new ArrayList<TreeNode>();
if(start>end){
res.add(null);
return res;
}
for(int i=start;i<=end;i++){
List<TreeNode> left = generateSub(start,i-1);
List<TreeNode> right = generateSub(i+1,end);
for(int t=0;t<left.size();t++){
for(int k=0;k<right.size();k++){
TreeNode root = new TreeNode(i);
root.left = left.get(t);
root.right = right.get(k);
res.add(root);
}
}
}
return res;
}
}
96. Unique Binary Search Trees
與95題類(lèi)似，不過(guò)只需要求解出樹(shù)的個(gè)數(shù)吵护，因此用動(dòng)態(tài)規(guī)劃即可盒音。
class Solution {
public int numTrees(int n) {
int[] G = new int[n+1];
G[0] = G[1] = 1;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++)
G[i] += (G[j-1] * G[i-j]);
}
return G[n];
}
}
98. Validate Binary Search Tree
注意，空樹(shù)也是平衡二叉樹(shù)馅而，我們用中序遍歷的方法祥诽，如果后面遍歷到的元素小于等于前面的元素，則返回false瓮恭。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if(root==null)
return true;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(root.left!=null){
stack.push(root.left);
root = root.left;
}
boolean hasPre = false;
int pre = Integer.MIN_VALUE;
while(!stack.isEmpty()){
TreeNode tmp = stack.pop();
if(!hasPre){
hasPre=true;
pre = tmp.val;
}
else{
if(tmp.val <= pre){
return false;
}
}
pre = tmp.val;
if(tmp.right!=null){
stack.push(tmp.right);
tmp = tmp.right;
while(tmp.left!=null){
stack.push(tmp.left);
tmp = tmp.left;
}
}
}
return true;
}
}
100. Same Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null)
return true;
else if(p==null || q==null)
return false;
else if(p.val != q.val)
return false;
else
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
101. Symmetric Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return helper(root,root);
}
public boolean helper(TreeNode node1,TreeNode node2){
if(node1 == null && node2 ==null)
return true;
else if(node1 == null || node2 == null || node1.val != node2.val)
return false;
return helper(node1.left,node2.right) && helper(node1.right,node2.left);
}
}
102. Binary Tree Level Order Traversal
樹(shù)的層次遍歷雄坪，這里我們只用到一個(gè)隊(duì)列，我們給每一行添加一個(gè)null屯蹦，來(lái)代表該行的結(jié)束维哈。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null)
return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
queue.offer(null);
while(!queue.isEmpty()){
List<Integer> row = new ArrayList<Integer>();
TreeNode tmp = queue.poll();
while(tmp!=null){
row.add(tmp.val);
if(tmp.left!=null) queue.offer(tmp.left);
if(tmp.right!=null) queue.offer(tmp.right);
tmp = queue.poll();
}
if(!queue.isEmpty()){
queue.offer(null);
}
res.add(row);
}
return res;
}
}
103. Binary Tree Zigzag Level Order Traversal
需要一個(gè)標(biāo)記來(lái)表示先放左子節(jié)點(diǎn)還是先放右子節(jié)點(diǎn)。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)
return res;
Stack<TreeNode> level = new Stack<TreeNode>();
level.push(root);
boolean flag = true;
while(!level.isEmpty()){
Stack<TreeNode> tmp = level;
level = new Stack<TreeNode>();
List<Integer> temp = new ArrayList<Integer>();
while(!tmp.isEmpty()){
TreeNode t = tmp.pop();
temp.add(t.val);
if(flag){
if(t.left != null)
level.push(t.left);
if(t.right != null)
level.push(t.right);
}
else{
if(t.right != null)
level.push(t.right);
if(t.left != null)
level.push(t.left);
}
}
flag = !flag;
res.add(temp);
}
return res;
}
}
104. Maximum Depth of Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)
return 0;
if(root.left==null && root.right==null)
return 1;
int left = root.left==null ? 0:maxDepth(root.left);
int right = root.right==null ? 0:maxDepth(root.right);
return Math.max(left,right) + 1;
}
}
105. Construct Binary Tree from Preorder and Inorder Traversal
根據(jù)前序遍歷和中序遍歷的結(jié)果重塑二叉樹(shù)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0; // Index of current root in inorder
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == root.val) {
inIndex = I;
}
}
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
return root;
}
}
106. Construct Binary Tree from Inorder and Postorder Traversal
從樹(shù)的后序遍歷和中序遍歷重建二叉樹(shù)登澜。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(postorder.length-1,0,inorder.length-1,inorder,postorder);
}
public TreeNode helper(int postEnd,int inStart,int inEnd,int[] inorder,int[] postorder){
if(postEnd < 0 || inStart > inEnd){
return null;
}
TreeNode root = new TreeNode(postorder[postEnd]);
int index = 0;
for(int i=inStart;i<=inEnd;i++){
if(inorder[i] == root.val){
index = I;
break;
}
}
root.left = helper(postEnd - inEnd + index-1,inStart,index-1,inorder,postorder);
root.right = helper(postEnd - 1,index+1,inEnd,inorder,postorder);
return root;
}
}
107. Binary Tree Level Order Traversal II
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(0, subList);
}
return wrapList;
}
}
108. Convert Sorted Array to Binary Search Tree
要保證是高度平衡的搜索二叉樹(shù)阔挠，只要每次從中間分裂即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums==null || nums.length==0)
return null;
return helper(nums,0,nums.length-1);
}
public TreeNode helper(int[] nums,int left,int right){
if(left > right)
return null;
int mid = (right - left ) /2 + left;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums,left,mid-1);
root.right = helper(nums,mid+1,right);
return root;
}
}
110. Balanced Binary Tree
判斷左右子樹(shù)的高度脑蠕，如果相差超過(guò)1购撼，則返回一個(gè)代表false的數(shù)字，下面的代碼中我們使用-1代表false。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root)!=-1;
}
public int height(TreeNode root){
if(root==null)
return 0;
int left = height(root.left);
int right = height(root.right);
if(left == -1 || right == -1 || Math.abs(left-right) > 1)
return -1;
return Math.max(left,right) + 1;
}
}
111. Minimum Depth of Binary Tree
遞歸求解份招，注意只有一個(gè)子樹(shù)的情況切揭。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root==null)
return 0;
if(root.left==null && root.right==null)
return 1;
int left = root.left==null?Integer.MAX_VALUE:minDepth(root.left);
int right = root.right==null?Integer.MAX_VALUE:minDepth(root.right);
return Math.min(left,right) + 1;
}
}
112. Path Sum
這里還是要注意，不能再輔助函數(shù)中使用root==null的條件锁摔，這樣在只有一個(gè)子樹(shù)的情況下會(huì)報(bào)錯(cuò)廓旬。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root==null)
return false;
return helper(root,sum);
}
public boolean helper(TreeNode root,int sum){
if(root.left==null && root.right==null && root.val==sum)
return true;
if(root.left!=null)
if(helper(root.left,sum-root.val))
return true;
if(root.right!=null)
if(helper(root.right,sum-root.val))
return true;
return false;
}
}
113. Path Sum II
回溯法的應(yīng)用,注意的是添加到返回結(jié)果的時(shí)候要新建一個(gè)ArrayList.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> res;
public List<List<Integer>> pathSum(TreeNode root, int sum) {
res = new ArrayList<List<Integer>>();
if(root==null)
return res;
helper(root,sum,new ArrayList<Integer>());
return res;
}
public void helper(TreeNode root,int sum,List<Integer> temp){
if(root.left==null && root.right==null && root.val == sum){
temp.add(root.val);
res.add(new ArrayList<Integer>(temp));
temp.remove(temp.size()-1);
return;
}
if(root.left!=null){
temp.add(root.val);
helper(root.left,sum-root.val,temp);
temp.remove(temp.size()-1);
}
if(root.right!=null){
temp.add(root.val);
helper(root.right,sum-root.val,temp);
temp.remove(temp.size()-1);
}
}
}
114. Flatten Binary Tree to Linked List
對(duì)左右子樹(shù)先分別進(jìn)行flatten操作，接下來(lái)就是要把左子樹(shù)接到右子樹(shù)上去谐腰，找到左子樹(shù)的最后一個(gè)節(jié)點(diǎn)读串，然后將左子樹(shù)插入根結(jié)點(diǎn)和右子樹(shù)之間淆院。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if(root==null)
return;
flatten(root.right);
if(root.left!=null){
flatten(root.left);
TreeNode tmp = root.left;
while(tmp.right!=null)
tmp = tmp.right;
tmp.right = root.right;
root.right = root.left;
root.left =null;
}
}
}
117. Populating Next Right Pointers in Each Node II
用一個(gè)隊(duì)列實(shí)現(xiàn)即可，隊(duì)列實(shí)現(xiàn)方式要注意。
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null)
return;
Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
queue.offer(root);
queue.offer(null);
while(!queue.isEmpty()){
TreeLinkNode tmp = queue.poll();
while(tmp!=null){
tmp.next = queue.peek();
if(tmp.left!=null)
queue.offer(tmp.left);
if(tmp.right!=null)
queue.offer(tmp.right);
tmp = queue.poll();
}
if(!queue.isEmpty())
queue.offer(null);
}
}
}
129. Sum Root to Leaf Numbers
遞歸的思路替饿，比較簡(jiǎn)單翅睛。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int res;
public int sumNumbers(TreeNode root) {
res = 0;
if(root==null)
return res;
helper(root,0);
return res;
}
public void helper(TreeNode root,int tmp){
if(root.left == null && root.right == null){
tmp = tmp * 10 + root.val;
res += tmp;
return;
}
if(root.left!=null)
helper(root.left,tmp * 10 + root.val);
if(root.right!=null)
helper(root.right,tmp * 10 + root.val);
}
}
144. Binary Tree Preorder Traversal
非遞歸前序遍歷二叉樹(shù)力喷。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode tmp = stack.pop();
res.add(tmp.val);
if(tmp.right!=null) stack.push(tmp.right);
if(tmp.left!=null) stack.push(tmp.left);
}
return res;
}
}
145. Binary Tree Postorder Traversal
后序遍歷一棵樹(shù)慷妙，非遞歸形式，用兩個(gè)棧芹枷。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null)
return res;
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
stack1.push(root);
while(!stack1.isEmpty()){
TreeNode tmp = stack1.pop();
stack2.push(tmp);
if(tmp.left!=null) stack1.push(tmp.left);
if(tmp.right!=null) stack1.push(tmp.right);
}
while(!stack2.isEmpty()){
res.add(stack2.pop().val);
}
return res;
}
}
173. Binary Search Tree Iterator
題目要求的空間復(fù)雜度是O(h)衅疙，因此stack中不能存儲(chǔ)太多的元素，因此將非遞歸中序遍歷二叉樹(shù)的過(guò)程拆開(kāi)鸳慈。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
if(root!=null){
stack.push(root);
while(root.left!=null){
stack.push(root.left);
root = root.left;
}
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
if(!stack.isEmpty()){
TreeNode tmp = stack.pop();
int val = tmp.val;
if(tmp.right!=null){
stack.push(tmp.right);
tmp = tmp.right;
while(tmp.left!=null){
stack.push(tmp.left);
tmp = tmp.left;
}
}
return val;
}
return 0;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
199. Binary Tree Right Side View
層次遍歷二叉樹(shù)饱溢，不過(guò)只保存每層的最后一個(gè)節(jié)點(diǎn)的值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null)
return res;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
queue.offer(null);
while(!queue.isEmpty()){
TreeNode tmp = queue.poll();
while(tmp!=null){
if(queue.peek()==null)
res.add(tmp.val);
if(tmp.left!=null) queue.offer(tmp.left);
if(tmp.right!=null) queue.offer(tmp.right);
tmp = queue.poll();
}
if(!queue.isEmpty()) queue.offer(null);
}
return res;
}
}
222. Count Complete Tree Nodes
如果是遍歷的話走芋，需要O(n)的復(fù)雜度绩郎，我們可以采用二分查找的思想，首先得到這個(gè)樹(shù)的高度翁逞，即一直往左走肋杖。然后判斷該高度下左子樹(shù)的最右邊的節(jié)點(diǎn)是否存在，如果存在挖函，那么左子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)是確定的状植，如果不存在，那么右子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)是確定的挪圾。接下來(lái)我們只需要繼續(xù)遞歸即可浅萧。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if(root==null)
return 0;
if(root.left==null && root.right==null)
return 1;
int height = 1;
TreeNode tmp = root;
while(tmp.left!=null){
height ++;
tmp = tmp.left;
}
int tmpHeight = 2;
tmp = root.left;
while(tmpHeight < height){
tmp = tmp.right;
tmpHeight++;
}
if(tmp==null)
return (int)Math.pow(2,height-2) + countNodes(root.left);
else
return (int)Math.pow(2,height-1) + countNodes(root.right);
}
}
226. Invert Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null)
return null;
TreeNode tmp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(tmp);
return root;
}
}
230. Kth Smallest Element in a BST
中序遍歷即可逐沙。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
if(root == null || k<=0)
return -1;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while(node!=null){
stack.push(node);
node = node.left;
}
int index = 0;
TreeNode res = new TreeNode(-1);
while(!stack.empty()){
node = stack.pop();
index++;
System.out.println(index + "" + k);
if(index==k){
res = node;
break;
}
node = node.right;
while(node!=null){
stack.push(node);
node = node.left;
}
}
return res.val;
}
}
235. Lowest Common Ancestor of a Binary Search Tree
/**
* 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.val - p.val) * (root.val - q.val) <= 0)
return root;
if(root.val > p.val)
return lowestCommonAncestor(root.left,p,q);
else
return lowestCommonAncestor(root.right,p,q);
}
}
236. Lowest Common Ancestor of a Binary Tree
此題的關(guān)鍵是判斷p和q分別位于哪棵子樹(shù)上哲思。
/**
* 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) return null;
if(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 root;
return left==null?right:left;
}
}
257. Binary Tree Paths
采用自底向上的策略，輸出所有的路徑吩案。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<String>();
if(root==null){
return res;
}
if(root.left==null && root.right==null){
res.add(""+root.val);
return res;
}
List<String> left = binaryTreePaths(root.left);
List<String> right = binaryTreePaths(root.right);
for(int i=0;i<left.size();i++){
res.add(root.val + "->" + left.get(i));
}
for(int i=0;i<right.size();i++){
res.add(root.val + "->" + right.get(i));
}
return res;
}
}
337. House Robber III
要么偷盜當(dāng)前根結(jié)點(diǎn)棚赔，要么不偷，分兩種情況進(jìn)行遞歸即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
if(root==null)
return 0;
int subfirst = root.val;
if(root.left!=null)
subfirst += (rob(root.left.left) + rob(root.left.right));
if(root.right!=null)
subfirst += (rob(root.right.left) + rob(root.right.right));
int subsecond = rob(root.left) + rob(root.right);
return Math.max(subfirst,subsecond);
}
}
404. Sum of Left Leaves
這里要求的是所有左葉子結(jié)點(diǎn)的和靠益，因此我們構(gòu)建了一個(gè)輔助函數(shù)丧肴，并傳入是否是左子節(jié)點(diǎn)。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null)
return 0;
return helper(root.left,true) + helper(root.right,false);
}
public int helper(TreeNode root,boolean isLeft){
if(root==null)
return 0;
if(root.left == null && root.right == null)
if(isLeft) return root.val;
else return 0;
return helper(root.left,true) + helper(root.right,false);
}
}
429. N-ary Tree Level Order Traversal
跟二叉樹(shù)的層次遍歷是一樣的胧后。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)
return res;
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
queue.offer(null);
while(!queue.isEmpty()){
Node tmp = queue.poll();
List<Integer> row = new ArrayList<Integer>();
while(tmp!=null){
row.add(tmp.val);
for(int i=0;i<tmp.children.size();i++){
queue.offer(tmp.children.get(i));
}
tmp = queue.poll();
}
res.add(row);
if(!queue.isEmpty()){
queue.offer(null);
}
}
return res;
}
}
437. Path Sum III
深度優(yōu)先遍歷的方法芋浮，注意的一個(gè)點(diǎn)是，路徑必須是連續(xù)的壳快，一旦以某個(gè)點(diǎn)開(kāi)始纸巷，那么路徑必須是連續(xù)的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) return 0;
return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
private int pathSumFrom(TreeNode node, int sum) {
if (node == null) return 0;
return (node.val == sum ? 1 : 0)
+ pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
}
}
