hot100之二叉树上
<h3 id="二叉树的中序队列094">二叉树的中序队列(094)</h3><p>先看代码</p>
<pre><code class="language-java">class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null){
if (root != null){
stack.add(root);
root = root.left;
}else {
TreeNode node = stack.pop();
res.add(node.val);
root = node.right;
}
}
return res;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过stack保存二叉树遍历栈, 反序遍历栈节点</p>
<h3 id="二叉树的最大深度104">二叉树的最大深度(104)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
int res = 0;
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int lefDepth = maxDepth(root.left);
int rigDepth = maxDepth(root.right);
return Math.max(lefDepth, rigDepth) + 1;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>递归调用自身</p>
<ul>
<li>感悟</li>
</ul>
<p>递归看的真的非常清爽, 写的也很清爽</p>
<h3 id="翻转二叉树226">翻转二叉树(226)</h3>
<p>省略</p>
<h3 id="对称二叉树101">对称二叉树(101)</h3>
<p>省略</p>
<h3 id="二叉树直径543">二叉树直径(543)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepthBinaryTree(root);
return res;
}
private int maxDepthBinaryTree(TreeNode node){
if (node == null) return 0;
int lefMax = maxDepthBinaryTree(node.left);
int rigMax = maxDepthBinaryTree(node.right);
res = Math.max(lefMax + rigMax, res);
return Math.max(lefMax, rigMax) + 1;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>增加了一个全局<code>res</code> 参数用于记录最大长度, 可能算是贪心</p>
<ul>
<li>感悟</li>
</ul>
<p>递归要维持一致的变量与传递参数, 单凭借自身的传递参数无法解决问题, 所以引入了<code>res</code> 全局变量</p>
<h3 id="二叉树的层序遍历102">二叉树的层序遍历(102)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res= new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.addFirst(root);
while (!queue.isEmpty()){
int n = queue.size();
List<Integer> layer = new ArrayList<>(n);
for (int i = 0; i < n; i++){
TreeNode node = queue.removeLast();
layer.add(node.val);
if (node.left != null)queue.addFirst(node.left);
if (node.right != null) queue.addFirst(node.right);
}
res.add(layer);
}
return res;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过双端队列, 左端入新端点, 右端出老端点, 每次<code>for</code> 循环, 一次性遍历完老端点</p>
<h3 id="将有序数组转换为二叉搜索树108">将有序数组转换为二叉搜索树(108)</h3>
<p>略</p>
<h3 id="验证二叉搜索树098">验证二叉搜索树(098)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode node, Integer max, Integer min){
if (node == null) return true;
int val = node.val;
if (max != null && val >= max) return false;
if (min != null && val <= min) return false;
return isValidBST(node.left, val, min) && isValidBST(node.right, max, val);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过函数传参 max, min</p>
<h3 id="二叉树搜索树中第k小的元素230">二叉树搜索树中第K小的元素(230)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
int k;
public int kthSmallest(TreeNode root, int k) {
this.k = k;
return dfs(root);
}
private int dfs(TreeNode node){
if (node == null) return -1;
int lefNode = dfs(node.left);
if (lefNode != -1) return lefNode;
if (--k == 0) return node.val;
return dfs(node.right);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>左根右的遍历方法</p>
<p>一开始使用<code>void dfs()</code>然后用 全局的<code>res</code> 来存储最终结果</p>
<p>但发现<code>void dfs()</code>的情况下, 递归不会因为得到<code>res</code> 后停止递归</p>
<p>而后选择 <code>int dfs()</code> 直接<code>return node.val</code> 避免后续没必要递归</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18926035
頁:
[1]