樹的遍歷方式總體分為兩類：深度優(yōu)先搜索（DFS）扔水、廣度優(yōu)先搜索（BFS）；
常見的 DFS ： 先序遍歷曹步、中序遍歷宪彩、后序遍歷；
前序遍歷：輸出順序：根節(jié)點(diǎn)讲婚、左子樹毯焕、右子樹
中序遍歷：輸出順序：左子樹、根節(jié)點(diǎn)磺樱、右子樹
后序遍歷：輸出順序：左子樹纳猫、右子樹、根節(jié)點(diǎn)
常見的 BFS ： 層序遍歷（即按層遍歷）竹捉。
劍指 Offer 27. 二叉樹的鏡像
- 時(shí)間復(fù)雜度：O(n)芜辕，空間復(fù)雜度：O(n)
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsepg3/
例如輸入：
4
2 7
1 3 6 9
鏡像輸出：
4
7 2
9 6 3 1
輸入：root = [4,2,7,1,3,6,9]
輸出：[4,7,2,9,6,3,1]
var mirrorTree = function(root) {
let res = null;
if(root != null){
res =new TreeNode(root.val);
res.left = mirrorTree(root.right);
res.right = mirrorTree(root.left);
}
return res
};
劍指 Offer 28. 對(duì)稱的二叉樹
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsrxq1/
- 時(shí)間復(fù)雜度：O(n)
var isSymmetric = function(root) {
if(root==null){
return true;
}
return dfs(root.left,root.right)
};
var dfs = function(t1, t2){
if(t1==null && t2==null) {return true}
if(t1==null|| t2==null) {return false}
if(t1.val != t2.val){return false}
return dfs(t1.left,t2.right) && dfs(t1.right,t2.left)
}
劍指 Offer 54. 二叉搜索樹的第 k 大節(jié)點(diǎn)
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xspy85/
- 時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)
- 二叉搜索樹：根節(jié)點(diǎn)的值大于其左子樹中任意一個(gè)節(jié)點(diǎn)的值块差，小于其右節(jié)點(diǎn)中任意一節(jié)點(diǎn)的值侵续，這一規(guī)則適用于二叉查找樹中的每一個(gè)節(jié)點(diǎn)。
- 二叉搜索樹的【中序遍歷】為 【遞增序列】憨闰，易得二叉搜索樹的 【中序遍歷倒序】 為 【遞減序列】 状蜗。
因此，求 “二叉搜索樹第 k大的節(jié)點(diǎn)” 可轉(zhuǎn)化為求 “此樹的【中序遍歷倒序】的第 k 個(gè)節(jié)點(diǎn)”鹉动。 中序遍歷 為 “左轧坎、根、右” 順序泽示，倒序就是“右缸血、根、左” 械筛。
時(shí)間復(fù)雜度：O(n)捎泻，空間復(fù)雜度：O(1)
var nums;
var res;
var kthLargest = function(root, k) {
nums = k
dfs(root);
return res;
};
var dfs = function(root){
if(root == null){
return;
}
dfs(root.right);
if(nums == 0){
return
}
nums --;
if(nums==0){
res = root.val
}
dfs(root.left)
}
劍指 Offer 55 - I. 二叉樹的深度
https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsaki2/
- 時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)
var maxDepth = function(root) {
if(root == null){
return 0
}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1
};
