三、二叉树
一、遞歸思想：遞歸的基本思想是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。在函數(shù)實現(xiàn)時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個解決問題的函數(shù)必須有明顯的結(jié)束條件，這樣就不會產(chǎn)生無限遞歸的情況了。（http://www.nowamagic.net/librarys/veda/detail/2314）
1）遍歷：結(jié)果在調(diào)用時作為參數(shù)傳遞；從頂?shù)较碌倪^程
2）分治：結(jié)果在返回值里，不在調(diào)用中作為參數(shù)傳遞，從下到上（有遞、無歸）
同：遞歸思想
90%二叉數(shù)問題都可分治解決
二叉樹問題：
1、樹形分析時間復雜度計算=樹中節(jié)點個數(shù)*每個節(jié)點的處理時間
2、二叉樹結(jié)構(gòu)：
* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* } View Code3、二叉樹遍歷：
遞歸：
1)前:跟-左-右
public class Solution {/*** @param root: The root of binary tree.* @return: Preorder in ArrayList which contains node values.*/public ArrayList<Integer> preorderTraversal(TreeNode root) {// write your code here//recursionArrayList<Integer> res = new ArrayList<>();if (root == null) {return res;}traverse(root,res);return res;}private void traverse(TreeNode root, ArrayList<Integer> res) {if (root == null) {return;}res.add(root.val);traverse(root.left, res);traverse(root.right, res);} } View Code2中：左-根-右
public class Solution {/*** @param root: The root of binary tree.* @return: Inorder in ArrayList which contains node values.*/public ArrayList<Integer> inorderTraversal(TreeNode root) {// write your code hereArrayList<Integer> result = new ArrayList<>();traverse(root, result);return result;}private void traverse(TreeNode root, ArrayList<Integer> result) {if (root == null) {return;}traverse(root.left, result);result.add(root.val);traverse(root.right,result);} } View Code3)后： 左- 右-中
public ArrayList<Integer> postorderTraversal(TreeNode root) {ArrayList<Integer> result = new ArrayList<Integer>();if (root == null) {return result;}result.addAll(postorderTraversal(root.left));result.addAll(postorderTraversal(root.right));result.add(root.val);return result; } View Code?
非遞歸
前：2遍，帶刷，not ac : root 和 treeNode 分錯
public class Solution {/*** @param root: The root of binary tree.* @return: Preorder in ArrayList which contains node values.*/public ArrayList<Integer> preorderTraversal(TreeNode root) {// write your code here//no - recusionArrayList<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root == null) {return result;}stack.push(root);while (!stack.empty()) {TreeNode treeNode = stack.pop();result.add(treeNode.val);if (treeNode.right != null) {stack.push(treeNode.right);}if (treeNode.left != null) {stack.push(treeNode.left);}}return result;} } View Code中：
public class Solution {/*** @param root: The root of binary tree.* @return: Inorder in ArrayList which contains node values.*/public ArrayList<Integer> inorderTraversal(TreeNode root) {// write your code hereArrayList<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode node = root;while (node != null || !stack.empty()) {while (node != null) {//遍歷到最左邊 stack.push(node);node = node.left;}node = stack.peek();//取出棧頂?shù)粍h除 stack.pop();result.add(node.val);//把最左邊的節(jié)點加入結(jié)果node = node.right;//該節(jié)點有右葉子嗎？ }return result;} } View Code后：not ac， 右回的時候忘了pop（）
public class Solution {/*** @param root: The root of binary tree.* @return: Postorder in ArrayList which contains node values.*/public ArrayList<Integer> postorderTraversal(TreeNode root) {// write your code hereArrayList<Integer> result = new ArrayList<>();if (root == null) {return result;}TreeNode cur = root;TreeNode pre = null;Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.empty()) {cur = stack.peek();// trarve up the tree, 深度遞歸if (pre == null || pre.left == cur || pre.right == cur) {if (cur.left != null) {stack.push(cur.left);} else if (cur.right != null){stack.push(cur.right);}} else if (cur.left == pre){//從左面回溯的if (cur.right != null) {stack.push(cur.right);}} else {//從右邊回溯的 result.add(cur.val);stack.pop();}pre = cur;}return result;} } View Code?
?4、二叉樹的最大深度:
(1) 分治法：ac
public class Solution {/*** @param root: The root of binary tree.* @return: An integer.*/private int depth;public int maxDepth(TreeNode root) {// write your code hereif (root == null) {return 0;}int left = maxDepth(root.left);int right = maxDepth(root.right);depth = Math.max(left, right) + 1;return depth;} } View Code（2）travese:not ac :curdepth是結(jié)果，被傳遞，不斷變化的
public class Solution {/*** @param root: The root of binary tree.* @return: An integer.*/private int depth;public int maxDepth(TreeNode root) {// write your code heredepth = 0;helper(root, 1);return depth;}private void helper (TreeNode root, int curdepth) {if (root == null) {return;}if (curdepth > depth) {depth = curdepth;}helper(root.left, curdepth + 1);helper(root.right, curdepth + 1);} } View Code5、Binary Tree Paths（http://www.lintcode.com/en/problem/binary-tree-paths/）：根節(jié)點到葉子節(jié)點的路徑
2遍，帶看，ac:?
分治法
public class Solution {/*** @param root the root of the binary tree* @return all root-to-leaf paths*/public List<String> binaryTreePaths(TreeNode root) {// Write your code here//分治法List<String> paths = new ArrayList<>();if (root == null) {return paths;}List<String> leftPaths = binaryTreePaths(root.left);List<String> rightPaths = binaryTreePaths(root.right);for (String path : leftPaths) {paths.add(root.val + "->" + path);}for (String path : rightPaths) {paths.add(root.val + "->" + path);}//root is a leafif (paths.size() == 0) {paths.add("" + root.val);}return paths;} } View Code 遍歷法：not ac, 節(jié)點.val,String.valueOf()不懂，注意第一個String.valueOf()一定有，不然無法變?yōu)樽址?/span> public class Solution {/*** @param root the root of the binary tree* @return all root-to-leaf paths*/public List<String> binaryTreePaths(TreeNode root) {// Write your code here//遍歷List<String> results = new ArrayList<>();if (root == null) {return results;}helper(root, String.valueOf(root.val), results);return results;}private void helper(TreeNode root, String path, List<String> results) {if (root == null) {return;}if (root.left == null && root.right == null) {results.add(path);return;}if (root.left != null) {helper(root.left, path + "->" + String.valueOf(root.left.val), results);}if (root.right != null) {helper(root.right, path + "->" + String.valueOf(root.right.val), results);}} } View Code?
6、Minimum Subtree（ http://www.lintcode.com/en/problem/minimum-subtree/）：
not ac : helper()返回錯誤，sum而不是subtreesum,sum下次還有繼續(xù)用；
第二遍：int sum = helper(root.left)+helper(root.right)+root.val，加了兩遍left. notac
思路：我們可以這樣考慮：對于每一個節(jié)點，
1. 如果它是空節(jié)點，那么就返回0
2. 如果它有左子數(shù)，那么加上左子樹的和
3. 如果它有右子樹，那么加上右子樹的和
簡單來說，對于任何一個節(jié)點，我們不去考慮它下面還有多少兒子，只是考慮和它直接接觸的左兒子和右兒子（如果存在的話）。如果到這個節(jié)點為止的和小于之前的和，那么就更新最小和，以及要回答的節(jié)點。
?7、判斷是否平衡二叉樹：
notac :class 要小寫
第一種：BOttom -UP o(n),o(n),當左子樹不平衡時，沒有必要再對右子樹求深度，要馬上 return -1，不可以把兩個判斷式寫在一起。
ResultType：class ResultType { int var1, var2; }---創(chuàng)建一個type類,一個默認方法包含，boolean,maxdepth, type helper():當子樹不是，根不是，空是，返回一個new type();
2遍，注意helper（）這個遞歸函數(shù)一定有一個終止條件，即對root== null 的處理在遞歸里。
class ResultType {public boolean isBalanced;public int maxDepth;public ResultType (boolean isBalanced, int maxDepth) {this.isBalanced = isBalanced;this.maxDepth = maxDepth;} } public class Solution {/*** @param root: The root of binary tree.* @return: True if this Binary tree is Balanced, or false.*/public boolean isBalanced(TreeNode root) {// write your code herereturn helper(root).isBalanced;}private ResultType helper(TreeNode root) {if (root == null) {//root 空，是平衡二叉樹return new ResultType (true, -1);}ResultType left = helper(root.left);ResultType right = helper(root.right);//leaf is not if (!left.isBalanced || !right.isBalanced) {return new ResultType(false, -1);}//root is notif (Math.abs(left.maxDepth - right.maxDepth) > 1) {return new ResultType(false, -1);}return new ResultType(true, Math.max(left.maxDepth, right.maxDepth) + 1);} } View Code第二種：Top-down Recursion Approach；Time Complexity : t:O(n^2),s:o(n),但是 maxDepth() 會一直重複呼叫導致有重複計算的部分。
構(gòu)建int maxdepth函數(shù)，返回值判斷 maxdepth != -1為真嗎。
public class Solution {/*** @param root: The root of binary tree.* @return: True if this Binary tree is Balanced, or false.*/public boolean isBalanced(TreeNode root) {// write your code herereturn maxDepth(root) != -1;}public int maxDepth(TreeNode root) {if (root == null) {return 0;}int left = maxDepth(root.left);int right = maxDepth(root.right);//leaf is not if (left == -1 || right == -1) {return -1;}//root is notif (Math.abs(left - right) > 1) {return -1;}return Math.max(left, right) + 1;} } View Code8、Subtree with Maximum Average ?http://www.lintcode.com/problem/subtree-with-maximum-average/?
遍歷+分治：遍歷:從上往下遞，分治從下往上的歸，求resultsum.
?
2.定義全局變量subtree，代表的是全局最大的average節(jié)點的信息，定義全局變量subtreeResult，內(nèi)部包含全局最大average節(jié)點的sum和size
3.定義一個返回值為ResultType的helper函數(shù)
4.將問題遞歸簡化，同時定義類型為ResultType的result變量，用于代表當前節(jié)點信息.
2,只能構(gòu)造一個resulttYpe類去處理。
public class Solution {/*** @param root the root of binary tree* @return the root of the maximum average of subtree*/ private class ResultType {int sum;int size;public ResultType(int sum, int size) {this.sum = sum;this.size = size;} }private TreeNode subtree = null;private ResultType subtreeSum = null;public TreeNode findSubtree2(TreeNode root) {// Write your code here helper(root);return subtree;}public ResultType helper(TreeNode root) {if (root == null) {return new ResultType (0, 0);}ResultType left = helper(root.left);ResultType right = helper(root.right);ResultType result = new ResultType(left.sum + right.sum + root.val,left.size + right.size + 1);if (subtree == null || subtreeSum.sum * result.size < result.sum * subtreeSum.size) {subtree = root;subtreeSum = result;}return result;} } View Code9、Flattern Binary Tree to Linked List http://www.lintcode.com/problem/flatten-binary-tree-to-linked-list/
1)、Non-Recursion
public class Solution {/*** @param root: a TreeNode, the root of the binary tree* @return: nothing*/public void flatten(TreeNode root) {// write your code here// no - curisionif (root == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.empty()) {TreeNode node = stack.pop();if (node.right != null) {stack.push(node.right);}if (node.left != null) {stack.push(node.left);}//connect:當前節(jié)點左制空，右邊為堆棧彈出的節(jié)點node.left = null;if (stack.empty()) {node.right = null;} else {node.right = stack.peek();}}} } View Code2)、traverse : 2 not ac，每次要存下右節(jié)點的值
查看http://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
blog:http://blog.csdn.net/linhuanmars/article/details/23717703 ? 遞歸思路很詳細：每次把pre 節(jié)點左節(jié)點制空，右節(jié)點置為當前節(jié)點。o(n),o(logn)
?
10.0、Lowest Common Ancestor http://www.lintcode.com/problem/lowest-common-ancestor/ (A,B都在樹中)
前提：A,B都在樹中
1）divide + conquer ：o(n)
public class Solution {/*** @param root: The root of the binary search tree.* @param A and B: two nodes in a Binary.* @return: Return the least common ancestor(LCA) of the two nodes.*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {// write your code here//divide + conquer o(n)if (root == null || root == A || root == B) {return root;}//divideTreeNode left = lowestCommonAncestor(root.left, A, B);TreeNode right = lowestCommonAncestor(root.right, A, B);//conquerif (left != null && right != null) {return root;}if (left != null) {return left;}if (right != null) {return right;}return null;} } View Code可以判定兩個都不在樹中
/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/ public class Solution {/*** @param root: The root of the binary search tree.* @param A and B: two nodes in a Binary.* @return: Return the least common ancestor(LCA) of the two nodes.*/public class Result {TreeNode node;boolean isAn;public Result (TreeNode node, boolean isAn) {this.node = node;this.isAn = isAn;}}public Result helper(TreeNode root, TreeNode A, TreeNode B) {// write your code here//divide + conquer o(n)if (root == null ) {return new Result(root, false);}if (root == A && root == B) {return new Result(root, true);}//divideResult left = helper(root.left, A, B);if (left.isAn) {return left;}Result right = helper(root.right, A, B);if (right.isAn) {return right;}//conquerif (left.node != null && right.node != null) {return new Result(root, true);} else if (root == A || root == B) {boolean isAncestor = left.node != null || right.node != null ? true :false;return new Result(root,isAncestor);} else {return new Result(left.node != null ?left.node : right.node, false);}}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B){Result is = helper(root, A, B);if (is.isAn) {return is.node;} else {return null; }} } View Code?
2）如果是二叉查找樹：
public int query(Node t, Node u, Node v) { int left = u.value; int right = v.value; //二叉查找樹內(nèi)，如果左結(jié)點大于右結(jié)點，不對，交換 if (left > right) { int temp = left; left = right; right = temp; } while (true) { //如果t小于u、v，往t的右子樹中查找 if (t.value < left) { t = t.right; //如果t大于u、v，往t的左子樹中查找 } else if (t.value > right) { t = t.left; } else { return t.value; } } } View Code?
10.1、最近公共祖先 II （每個節(jié)點除了左右兒子指針以外，還包含一個父親指針parent，指向自己的父親。）
思路：舉例，找A，B的最近公共祖先。相當于找兩個單鏈表的公共節(jié)點，用ArrayList<TreeNode> pathA,pathB 記錄從A開始到根節(jié)點的路徑，然后比較兩個path的找出第一個不同的節(jié)點。
/*** Definition of ParentTreeNode:* * class ParentTreeNode {* public ParentTreeNode parent, left, right;* }*/ public class Solution {/*** @param root: The root of the tree* @param A, B: Two node in the tree* @return: The lowest common ancestor of A and B*/public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,ParentTreeNode A,ParentTreeNode B) {// Write your code here ArrayList<ParentTreeNode> pathA = getParentPath2(A);ArrayList<ParentTreeNode> pathB = getParentPath2(B);int indexA = pathA.size() - 1;int indexB = pathB.size() - 1;ParentTreeNode ancestor = null;while (indexA >= 0 && indexB >= 0) {if (pathA.get(indexA) != pathB.get(indexB)) {break;}ancestor = pathA.get(indexA);indexA--;indexB--;}return ancestor;}public ArrayList<ParentTreeNode> getParentPath2 (ParentTreeNode root) {ArrayList<ParentTreeNode> path = new ArrayList<ParentTreeNode>();while (root != null) {path.add(root);root = root.parent;}return path;} } View Code10.3?最近公共祖先 III （A，B可能都不在樹里）
?
/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/class ResultType {public boolean a_exist, b_exist;public TreeNode node;ResultType(boolean a, boolean b, TreeNode n) {a_exist = a;b_exist = b;node = n;} }public class Solution {/*** @param root The root of the binary tree.* @param A and B two nodes* @return: Return the LCA of the two nodes.*/public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode A, TreeNode B) {// write your code hereResultType rt = helper(root, A, B);if (rt.a_exist && rt.b_exist)return rt.node;elsereturn null;}public ResultType helper(TreeNode root, TreeNode A, TreeNode B) {if (root == null)return new ResultType(false, false, null);ResultType left_rt = helper(root.left, A, B);ResultType right_rt = helper(root.right, A, B);boolean a_exist = left_rt.a_exist || right_rt.a_exist || root == A;boolean b_exist = left_rt.b_exist || right_rt.b_exist || root == B;if (root == A || root == B)return new ResultType(a_exist, b_exist, root);if (left_rt.node != null && right_rt.node != null)return new ResultType(a_exist, b_exist, root);if (left_rt.node != null)return new ResultType(a_exist, b_exist, left_rt.node);if (right_rt.node != null)return new ResultType(a_exist, b_exist, right_rt.node);return new ResultType(a_exist, b_exist, null);} } View Code?
11、Binary Tree Longest Consecutive Sequence http://www.lintcode.com/problem/binary-tree-longest-consecutivesequence/
public class Solution {/*** @param root the root of binary tree* @return the length of the longest consecutive sequence path*/public int longestConsecutive(TreeNode root) {//tranverse + dividereturn helper(root, null, 0);}public int helper(TreeNode root, TreeNode parent, int lengthwithoutroot) {if (root == null) {return 0;}int length = (parent != null && parent.val + 1 == root.val) ? lengthwithoutroot + 1 : 1;int left = helper(root.left, root, length);int right = helper(root.right, root, length);return Math.max(length, Math.max(left,right));} } View Code12、Binary Tree Path Sum I?http://www.lintcode.com/problem/binary-tree-path-sum/ ? 從根出發(fā)
not ac：is leaf?
public class Solution {/*** @param root the root of binary tree* @param target an integer* @return all valid paths*/public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {// Write your code hereList<List<Integer>> results = new ArrayList<>();if (root == null) {return results;}List<Integer> path = new ArrayList<Integer>();path.add(root.val);helper(root, root.val, path, results, target);return results;}private void helper(TreeNode root, int sum,List<Integer> path, List<List<Integer>> results,int target) {//meet leaf if (root.left == null && root.right == null) {if (sum == target) {results.add(new ArrayList<Integer>(path));}}//go leftif (root.left != null) {path.add(root.left.val);helper(root.left, sum + root.left.val, path, results, target);path.remove(path.size() - 1);}//go rightif (root.right != null) {path.add(root.right.val);helper(root.right, sum + root.right.val, path, results, target);path.remove(path.size() - 1);}} } View Code13、Binary Tree Path SumII ?http://www.lintcode.com/problem/binary-tree-path-sum-ii/ ?任意節(jié)點出發(fā)，但是層級遞增的
public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {// Write your code hereList<List<Integer>> results = new ArrayList<>();if (root == null) {return results;}List<Integer> path = new ArrayList<>();helper(root, target, path, results, 0);return results;}private void helper(TreeNode head, int sum,List<Integer> path,List<List<Integer>> results, int level) {if (head == null) {return;}int temp = sum;path.add(head.val);for (int i = level; i >= 0; i--) {temp -= path.get(i);if (temp == 0) {List<Integer> tmp = new ArrayList<Integer> ();for (int j = i; j <= level; j++) {tmp.add(path.get(j));}results.add(tmp);}}helper(head.left, sum, path, results, level + 1);helper(head.right, sum, path, results, level + 1);path.remove(path.size() - 1);} } View Code14.Binary Tree Path SumIII ?
public class Solution {/*** @param root the root of binary tree* @param target an integer* @return all valid paths*/public List<List<Integer>> binaryTreePathSum3(ParentTreeNode root, int target) {// Write your code hereList<List<Integer>> results = new ArrayList<>();dfs(root, target, results);return results;}private void dfs(ParentTreeNode root, int target, List<List<Integer>> results) {if (root == null) {return;}List<Integer> path = new ArrayList<Integer>();findSum(root, null, path, results, target);dfs(root.left, target, results);dfs(root.right, target, results);}private void findSum(ParentTreeNode root, ParentTreeNode father,List<Integer> path, List<List<Integer>> results, int target) {path.add(root.val);target -= root.val;if (target == 0) {List<Integer> tmp = new ArrayList<Integer>();Collections.addAll(tmp, new Integer [path.size()]);Collections.copy(tmp, path);results.add(tmp);}if (root.parent != null && root.parent != father) {findSum(root.parent, root, path, results, target);}if (root.left != null && root.left != father) {findSum(root.left, root, path, results, target);}if (root.right != null && root.right != father) {findSum(root.right, root, path, results, target);}path.remove(path.size() - 1);} } View Code三、二叉查找樹：
性質(zhì)：1.左子樹小于跟
從定義出發(fā)： ? 左子樹都比根節(jié)點小 ?left <= root
? 右子樹都不小于根節(jié)點 root < right
從效果出發(fā)： ? 中序遍歷 in-order traversal 是“不下降”序列
?? 如果一棵二叉樹的中序遍歷不是“不下降”序列，則一定不是BST
? 如果一棵二叉樹的中序遍歷是不下降，也未必是BST
?
1、Validate Binary Search Tree http://www.lintcode.com/problem/validate-binary-search-tree/ (都是嚴格小于和大于)
方法一：一個變量last存放當上一個節(jié)點的值，中序遍歷二叉樹，比較當前節(jié)點和last，但無法處理 ?【10，#，20】和【10，20】的情況 ，只能當滿足 root.left < root <root.right適用
not ac :int ---long ,對當前節(jié)點判斷應(yīng)該是《=
public class Solution {/*** @param root: The root of binary tree.* @return: True if the binary tree is BST, or false*/public long last = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {// write your code hereif (root == null) {return true;}//檢查左子樹if (!isValidBST(root.left)) {return false;}//檢查當前節(jié)點if (root.val <= last) {return false;}last = root.val;//檢查右子樹if (!isValidBST(root.right)) {return false;}return true;} } View Code?
方法二：最大、最小法：min = INTEGER.MIN,max =INTEGER.MAX,每個節(jié)點都進行判斷 ?cur.left <= cur<cur.right當進入左子樹，更新min,當進入右子樹更新max
not ac : int 換為 long
public class Solution {/*** @param root: The root of binary tree.* @return: True if the binary tree is BST, or false*/private long min = Long.MIN_VALUE;private long max = Long.MAX_VALUE;public boolean isValidBST(TreeNode root) {// write your code herereturn isValidhelper(root, min, max);}private boolean isValidhelper(TreeNode root, long min, long max) {if (root == null) {return true;}if (root.val <= min || root.val >= max) {return false;}if (!isValidhelper(root.left, min, root.val) || !isValidhelper(root.right, root.val, max)){return false;}return true;} } View Code?2、Convert Binary Search Tree to Doubly Linked List ? ?http://www.lintcode.com/problem/convert-binary-search-tree-to-do ubly-linked-list/
?
轉(zhuǎn)載于:https://www.cnblogs.com/lingli-meng/p/6532628.html
總結(jié)
- 上一篇： 推荐一款移动端日历App吉日历
- 下一篇： javascript经典广告代码.rar