hot100之二叉树下
<h3 id="二叉树的右视图199">二叉树的右视图(199)</h3><pre><code class="language-java">class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0);
return res;
}
private void dfs(TreeNode node, int depth){
if (node == null) return;
if (res.size() == depth){
res.add(node.val);
}
dfs(node.right, depth+1);
dfs(node.left, depth+1);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>因为一层只需要一个节点, 以depth作为限制</p>
<h3 id="二叉树展开为链表114">二叉树展开为链表(114)</h3>
<pre><code class="language-java">class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.left);
flatten(root.right);
TreeNode lef = root.left;
TreeNode rig = root.right;
root.left = null;
root.right = lef;
TreeNode curr = root;
while (curr.right != null){
curr = curr.right;
}curr.right = rig;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>将左子树截断放到右端, 再将右子树放在左子树末尾</p>
<p>因为递归原因, 左子树必然为链表</p>
<h3 id="从前序与中序遍历序列构造二叉树105">从前序与中序遍历序列构造二叉树(105)</h3>
<pre><code class="language-java">class Solution {
Map<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
map = new HashMap<>();
for (int i = 0; i < n; i++){
map.put(inorder, i);
}
return dfs(preorder, 0, n, 0, n);
}
private TreeNode dfs(int[] preorder, int lefPre, int rigPre, int lefIn, int rigIn){
if (lefPre == rigPre) return null;
int lefSize = map.get(preorder) - lefIn;
TreeNode lefNode = dfs(preorder, lefPre+1, lefPre+1+lefSize, lefIn, lefIn+lefSize);
TreeNode rigNode = dfs(preorder, lefPre+1+lefSize, rigPre, lefIn+1+lefSize, rigIn);
return new TreeNode(preorder, lefNode, rigNode);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>以前序遍历取根, 切分中序遍历的左右子树作构造</p>
<h3 id="路径总和437">路径总和(437)</h3>
<pre><code class="language-java">class Solution {
Map<Long, Integer> map = new HashMap<>();
int res;
public int pathSum(TreeNode root, int targetSum) {
map.put(0L,1);
dfs(root, targetSum, 0L);
return res;
}
private void dfs(TreeNode node, int targetSum, long subSum){
if (node == null) return;
subSum += node.val;
if (map.containsKey(subSum - targetSum)) res +=map.get(subSum - targetSum);
map.put(subSum, map.getOrDefault(subSum, 0)+1);
dfs(node.left, targetSum, subSum);
dfs(node.right, targetSum, subSum);
map.put(subSum, map.get(subSum)-1);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>又是一个前缀和题目</p>
<h3 id="二叉树的最近公共祖先236">二叉树的最近公共祖先(236)</h3>
<pre><code class="language-java">class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root) return root;
TreeNode lefNode = lowestCommonAncestor(root.left, p, q);
TreeNode rigNode = lowestCommonAncestor(root.right, p, q);
if (lefNode == null && rigNode == null) return null;
if (lefNode != null && rigNode != null) return root;
return lefNode != null ? lefNode : rigNode;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>找到子节点向上return, 两节点未相遇则继续向上return</p>
<ul>
<li>感悟</li>
</ul>
<p>二叉树题目要注意需要返回给父节点的元素</p>
<h3 id="二叉树中的最大路径和124">二叉树中的最大路径和(124)</h3>
<pre><code class="language-java">class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}
private int dfs(TreeNode node){
if (node == null) return 0;
int lefMax = Math.max(dfs(node.left), 0);
int rigMax = Math.max(dfs(node.right), 0);
res = Math.max(res, lefMax+ node.val + rigMax);
return Math.max(lefMax, rigMax) + node.val;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>以单向链作返回父节点元素, 取 左右链+节点 与记录的最大值作对比</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18928278
頁:
[1]