1.1、題目1
劍指 Offer 54. 二叉搜索樹的第k大節點
1.2、解法
res和k設為全域變數，然后開始遍歷二叉搜索樹，
因為是二叉搜索樹，所以從右結點開始遍歷，
每次遍歷就判斷是否到達結點，
每個結點就-k，知道到達結點，
1.3、代碼
class Solution {
int res,k;
public int kthLargest(TreeNode root, int k) {
this.k=k;
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root==null) return ;
dfs(root.right);
if(k==0) return;
if(--k==0) res=root.val;
dfs(root.left);
}
}
2.1、題目2
劍指 Offer 36. 二叉搜索樹與雙向鏈表
2.2、解法
深度優先搜索，，通過前后結點開始賦值，
搜索時，中序遍歷，如果該結點不為空，
則pre結點的right為當前結點，該節點的left為pre
然后pre結點變為當前節點，到下一個結點繼續遍歷
2.3、代碼
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if(cur == null) return;
dfs(cur.left);
if(pre != null) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
3.1、題目3
劍指 Offer 34. 二叉樹中和為某一值的路徑
3.2、解法
這里有點像回溯加減枝的感覺
如果到達葉子結點，并且路線結點值加起來是target值就添加入List中
這里結束要將添加的值洗掉掉，從而進入下個階段，
3.3、代碼
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
void recur(TreeNode root, int tar) {
if(root == null) return;
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null)
res.add(new LinkedList(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/300373.html
標籤：其他
上一篇：C語言 ##__VA_ARGS__ - C語言零基礎入門教程
下一篇：十大開源軟體基金會你知道哪些？