# 总结：二叉树的属性

## 是否对称 ### 思路

• 左节点为空，右节点不为空，返回 false，左节点不为空，右节点为空，返回 false；
• 左右节点均不为空，但数值不同，返回 false；
• 如果左右节点均为空，则返回 true；

• 如果以上条件均不满足，则再进入递归逻辑

### 代码实现

``` public boolean isSymmetric1(TreeNode root) { return compare(root.left, root.right); }

``````private boolean compare(TreeNode left, TreeNode right) {

if (left == null && right != null) {
return false;
}
if (left != null && right == null) {
return false;
}

if (left == null && right == null) {
return true;
}
if (left.val != right.val) {
return false;
}
// 比较外侧
boolean compareOutside = compare(left.left, right.right);
// 比较内侧
boolean compareInside = compare(left.right, right.left);
return compareOutside && compareInside;
}
``````

```

## 二叉树的最大深度

### 给定一个二叉树，找出其最大深度。

#### 思路

1. 递归函数的传入的参数为二叉树的根节点，返回值为二叉树的高度；
2. 递归的终止条件为当节点为空节点时，返回高度为 0；
3. 先求出它左子树的高度，然后再求出它右子树的高度，俩高度的最大值+1为二叉树的最大深度。

```java class solution { public: int getdepth(treenode node) { if (node == null) return 0; int leftdepth = getdepth(node.left); // 左 int rightdepth = getdepth(node.right); // 右 int depth = 1 + Math.max(leftdepth, rightdepth); // 中 return depth; } int maxdepth(treenode root) { return getdepth(root); } };```

```java // Definition for a Node. class Node { public int val; public List children;

``````public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
``````

};

class Solution { public int maxDepth(Node root) { if (root == null) { return 0; } else if (root.children.isEmpty()) { return 1;
} else { List heights = new LinkedList<>(); // 循环求出每个子树的高度 for (Node item : root.children) { heights.add(maxDepth(item)); } return Collections.max(heights) + 1; } } }

```

## 二叉树的最小深度

```java class Solution { /** * 递归法，相比求MaxDepth要复杂点 * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量 */ public int minDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = minDepth(root.left); int rightDepth = minDepth(root.right); if (root.left == null) { return rightDepth + 1; } if (root.right == null) { return leftDepth + 1; } // 左右结点都不为null return Math.min(leftDepth, rightDepth) + 1; } }```

## 求二叉树有多少个节点

```java class solution { public: int getdepth(treenode node) { if (node == null) return 0; int leftdepth = getdepth(node.left); // 左 int rightdepth = getdepth(node.right); // 右 int depth = 1 + leftdepth, rightdepth; // 中 return depth; } int maxdepth(treenode root) { return getdepth(root); } };```

## 平衡二叉树

### 思路

1. 明确递归函数的参数和返回值，参数为传入的根节点，如果左右子树的返回值 > 1,则我们返回 -1，表示已经不是平衡二叉树了；
2. 递归的终止条件为遇到了空节点，则 return 0, 表示当前节点为 根节点，高度为 0；
3. 单层递归逻辑为，分别求出左右子树的高度，如果差值小于等于 1，则返回当前二叉树的高度，否则返回 -1，表示已经不是二叉树了；

``` class Solution { /* * 递归法 / public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; }

``````private int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = getHeight(root.right);
if (rightHeight == -1) {
return -1;
}
// 左右子树高度差大于1，return -1表示已经不是平衡树了
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return Math.max(leftHeight, rightHeight) + 1;
}
``````

} ```

## 二叉树的所有路劲

### 思路

1. 确定递归的参数和返回值，参数为传入的根节点，记录每条路径的节点值数组path，以及路径结果数组res；
2. 当遇到叶子节点的时候终止，并将路径节点值数组里的数值转换成字符串，然后加入到结果数组；
3. 递归的单层逻辑为，因为是前序遍历：中-左-右，所以先处理中间节点，加入到 path 中，然后再递归处理左子树和右子树，并递归完后回溯；

``` //解法一 class Solution { /* * 递归法 / public List binaryTreePaths(TreeNode root) { List res = new ArrayList<>(); if (root == null) { return res; } List paths = new ArrayList<>(); traversal(root, paths, res); return res; }

``````private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
// 叶子结点
if (root.left == null && root.right == null) {
// 输出
StringBuilder sb = new StringBuilder();
for (int i = 0; i < paths.size() - 1; i++) {
sb.append(paths.get(i)).append("->");
}
sb.append(paths.get(paths.size() - 1));
return;
}
if (root.left != null) {
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
if (root.right != null) {
traversal(root.right, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
}
``````

} ```

## 左叶子之和

### 思路

```if (root.left != null && root.left.left == null && root.left.right == null) { // 中 midValue = root.left.val; }```

``` class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) return 0; int leftValue = sumOfLeftLeaves(root.left); // 左 int rightValue = sumOfLeftLeaves(root.right); // 右

``````    int midValue = 0;
if (root.left != null && root.left.left == null && root.left.right == null) { // 中
midValue = root.left.val;
}
int sum = midValue + leftValue + rightValue;
return sum;
}
``````

} ```

## 左下角的值

### 思路

1. 明确递归函数的参数和返回值：参数为传入的根节点，以及一个int型变量用来记录最长深度。返回值为 void；
2. 当遇到叶子节点的时候，为终止条件，并开始统计最大深度；
3. 确定单层递归逻辑，当不是叶子节点时，则继续遍历左子树和右子树，并记得要回溯；

```java // 递归法 class Solution { private int Deep = -1; private int value = 0; public int findBottomLeftValue(TreeNode root) { value = root.val; findLeftValue(root,0); return value; }

``````private void findLeftValue (TreeNode root,int deep) {
if (root == null) return;
if (root.left == null && root.right == null) {
if (deep > Deep) {
value = root.val;
Deep = deep;
}
}
if (root.left != null) findLeftValue(root.left,deep + 1);
if (root.right != null) findLeftValue(root.right,deep + 1);
}
``````

} ```

## 路劲总和 1

### 思路

1. 确定递归函数的传参和返回值：参数为传入的根节点和计数变量，该计数变量每次递归的时候需要减去当前节点的值，最后遇到叶子节点的时候判断该叶子节点的值是否与它一致，如果一致，则表示找到了该路径。返回值为bool类型；
2. 递归函数的终止条件为：当遇到叶子节点的时候，并且计数变量等于叶子节点的值就返回 true;
3. 单层递归逻辑为：遍历左子树和右子树，并回溯

```java class solution { public boolean haspathsum(treenode root, int targetsum) { if (root == null) { return false; } targetsum -= root.val; // 叶子结点 if (root.left == null && root.right == null) { return targetsum == 0; } if (root.left != null) { boolean left = haspathsum(root.left, targetsum); if (left) {// 已经找到 return true; } } if (root.right != null) { boolean right = haspathsum(root.right, targetsum); if (right) {// 已经找到 return true; } } return false; } }

// 精简后的代码

class solution { public boolean haspathsum(treenode root, int targetsum) {

``````    if (root == null) return false; // 为空退出

// 叶子节点判断是否符合
if (root.left == null && root.right == null) return root.val == targetsum;

// 求两侧分支的路径和
return haspathsum(root.left, targetsum - root.val) || haspathsum(root.right, targetsum - root.val);
}
``````

} ```

## 路径总和2

### 思路

```java class solution { public list> pathsum(treenode root, int targetsum) { list> res = new arraylist<>(); if (root == null) return res; // 非空判断

``````    list<integer> path = new linkedlist<>();
preorderdfs(root, targetsum, res, path);
return res;
}

public void preorderdfs(treenode root, int targetsum, list<list<integer>> res, list<integer> path) {
// 遇到了叶子节点
if (root.left == null && root.right == null) {
// 找到了和为 targetsum 的路径
if (targetsum - root.val == 0) {
}
return; // 如果和不为 targetsum，返回
}

if (root.left != null) {
preorderdfs(root.left, targetsum - root.val, res, path);
path.remove(path.size() - 1); // 回溯
}
if (root.right != null) {
preorderdfs(root.right, targetsum - root.val, res, path);
path.remove(path.size() - 1); // 回溯
}
}
``````

} ```

1. 阅读完记得给我点个赞哦，有👍 有动力
2. 关注公众号--- HelloWorld杰少，第一时间推送新姿势

「其他文章」
{"ft_lang_label":"__label__zh","ft_lang_prob":0.59886706,"math_prob":0.9930775,"size":9258,"snap":"2022-40-2023-06","text_gpt3_token_len":5342,"char_repetition_ratio":0.16436136,"word_repetition_ratio":0.2374894,"special_character_ratio":0.28677902,"punctuation_ratio":0.18049793,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98859215,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,2,null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-02-01T02:13:55Z\",\"WARC-Record-ID\":\"<urn:uuid:8324a81a-cde5-47b5-b16a-4f723b3cdfa5>\",\"Content-Length\":\"42611\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:6591b9e7-2734-4e89-867b-14819a1b77cb>\",\"WARC-Concurrent-To\":\"<urn:uuid:638a1855-e661-441a-ab37-49ec9bf023b6>\",\"WARC-IP-Address\":\"172.66.40.196\",\"WARC-Target-URI\":\"https://www.gushiciku.cn/pl/aSLP\",\"WARC-Payload-Digest\":\"sha1:QHHEGC4SA4JP43UKOGNHZAAIXMH3NTAW\",\"WARC-Block-Digest\":\"sha1:AHPDX2PCHVP2NYRVM5F6SIZP4ITHQ5JK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-06/CC-MAIN-2023-06_segments_1674764499899.9_warc_CC-MAIN-20230201013650-20230201043650-00612.warc.gz\"}"}