樹的遍歷方式總體分為兩類:深度優(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
};