重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路分析
根据中序遍历和前序遍历可以确定二叉树，具体过程为：
- 根据前序序列第一个结点确定根结点
- 根据根结点在中序序列中的位置分割出左右两个子序列
- 对左子树和右子树分别递归使用同样的方法继续分解‘
例如：
前序序列{1,2,4,7,3,5,6,8} = pre
中序序列{4,7,2,1,5,3,8,6} = in
1、根据当前前序序列的第一个结点确定根结点，为 1
2、找到 1 在中序遍历序列中的位置，为 in[3]
3、切割左右子树，则 in[3] 前面的为左子树， in[3] 后面的为右子树
4、则切割后的左子树前序序列为：{2,4,7}，切割后的左子树中序序列为：{4,7,2}；切割后的右子树前序序列为：{3,5,6,8}，切割后的右子树中序序列为：{5,3,8,6}
5、对子树分别使用同样的方法分解
代码实现
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre.length == 0 || in.length == 0) {
return null;
}
TreeNode root = new TreeNode(pre[0]);
for (int i=0; i<in.length; i++) {
// 在中序中找到前序的根
if (in[i] == pre[0]) {
// 左子树，注意 copyOfRange 函数，左闭右开
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
// 右子树，注意 copyOfRange 函数，左闭右开
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
break;
}
}
return root;
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null; #指向父结点的指针
TreeLinkNode(int val) {
this.val = val;
}
}解法1 还原二叉树
思路分析
既然给了二叉树的某个结点，且二叉树存储着指向父结点的指针（next），那我们可以先找到根节点，再对树进行中序遍历，最后根据中序遍历结果找到给定结点的下一结点。
代码实现
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
static ArrayList<TreeLinkNode> list = new ArrayList();
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
TreeLinkNode par = pNode;
//先找根结点
while (par.next != null) {
par = par.next;
}
//再进行中序遍历
InOrder(par);
//返回下一个结点
for (int i=0; i<list.size(); i++) {
if (pNode == list.get(i)) {
return i == list.size()-1 ? null : list.get(i+1);
}
}
return null;
}
//二叉树中序遍历
void InOrder(TreeLinkNode pNode) {
if (pNode != null) {
InOrder(pNode.left);
list.add(pNode);
InOrder(pNode.right);
}
}
}复杂度
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
解法2 直接找下一结点
思路分析1
以该二叉树为例，中序遍历为：{D,B,H,E,I,A,F,C,G}
仔细观察，可以把中序下一结点归为几种类型：
有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H。
无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E。
无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点。
代码实现
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
// 1.有右子树，下一结点是右子树中的最左结点
if (pNode.right != null) {
TreeLinkNode pRight = pNode.right;
while (pRight.left != null) {
pRight = pRight.left;
}
return pRight;
}
// 2.无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点
if (pNode.next != null && pNode.next.left == pNode) {
return pNode.next;
}
// 3.无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到
// 某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点
if (pNode.next != null) {
TreeLinkNode pNext = pNode.next;
while (pNext.next != null && pNext.next.right == pNext) {
pNext = pNext.next;
}
return pNext.next;
}
return null;
}
}思路分析2
我们先来回顾一下中序遍历的过程：先遍历树的左子树，再遍历根节点，最后再遍历右子树。所以最左节点是中序遍历的第一个节点。
代码实现
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if (pNode.right != null) {
TreeLinkNode node = pNode.right;
while (node.left != null) {
node = node.left;
}
return node;
} else {
while (pNode.next != null) {
TreeLinkNode parent = pNode.next;
if (parent.left == pNode) {
return parent;
}
pNode = pNode.next;
}
}
return null;
}
}复杂度
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(1) |
二叉树镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5
思路分析
交换左右子树的节点，然后递归调用该方法。
代码实现
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if (root == null)
return;
swap(root);
Mirror(root.left);
Mirror(root.right);
}
private void swap(TreeNode root) {
TreeNode node = root.left;
root.left = root.right;
root.right = node;
}
}对称的二叉树
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
解法1 递归
思路分析
根节点的左右子树相同，左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同即可。
代码实现
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if (pRoot == null) {
return true;
}
return isSymmetrical(pRoot.left, pRoot.right);
}
boolean isSymmetrical(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
if (left.val == right.val) {
return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left);
}
return false;
}
}解法2 非递归
思路分析
采用栈或队列存取各级子树根节点。
代码实现
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.Stack;
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if (pRoot == null)
return true;
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(pRoot.left);
s.push(pRoot.right);
while (!s.isEmpty()) {
TreeNode right = s.pop();
TreeNode left = s.pop();
if (right == null && left == null)
continue;
if (right == null || left == null)
return false;
if (right.val != left.val)
return false;
s.push(left.left);
s.push(right.right);
s.push(left.right);
s.push(right.left);
}
return true;
}
}104 二叉树的高度
题目描述
给定一个二叉树，找出其最大深度。
思路分析
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数，使用递归解决问题。使用DFS（深度优先搜索）策略。
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.lang.Math;
class Solution {
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}复杂度
| 时间复杂度 | O(N) N为结点数 |
|---|---|
| 空间复杂度 | O(log(N)) |
110 平衡二叉树
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true
解法1 自顶向下（暴力法）
构造一个获取当前节点最大深度的方法 depth(root) ，通过比较此子树的左右子树的最大高度差abs(depth(root.left) - depth(root.right))，来判断此子树是否是二叉平衡树。若树的所有子树都平衡时，此树才平衡。
此方法容易想到，但会产生大量重复计算，时间复杂度较高。
实现代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}复杂度分析
| 时间复杂度 | O(nlgn) |
|---|---|
| 空间复杂度 | O(n) |
解法2 自底向上
对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
代码实现
class Solution {
public boolean isBalanced(TreeNode root) {
return recur(root) != -1;
}
private int recur(TreeNode root) {
if (root == null) return 0;
int left = recur(root.left);
if (left == -1) return -1;
int right = recur(root.right);
if (right == -1) return -1;
return Math.abs(left - right)<2 ? Math.max(left,right)+1 : -1;
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
在IntelliJ IDEA中测试
package com.cn.algorithm;
/**
* @Author: cyh
* @Description: 平衡二叉树
**/
public class isBalancedDemo {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
/**
* 自顶向下
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int depth(TreeNode root) {
if (root == null)
return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
/**
* 自底向上
* @param root
* @return
*/
public boolean isBalanced(TreeNode root) {
return recur(root) != -1;
}
private int recur(TreeNode root) {
if (root == null) return 0;
int left = recur(root.left);
if (left == -1) return -1;
int right = recur(root.right);
if (right == -1) return -1;
return Math.abs(left - right)<2 ? Math.max(left,right)+1 : -1;
}
TreeNode arrayToTree(Integer[] array, int index) {
TreeNode root = null;
if (index < array.length) {
Integer value = array[index];
if (value == null) {
return null;
}
root = new TreeNode(value);
root.left = arrayToTree(array, 2*index + 1);
root.right = arrayToTree(array, 2*index + 2);
return root;
}
return root;
}
public static void main(String[] args) {
isBalancedDemo demo = new isBalancedDemo();
Integer[] arr = {3,9,20,null,null,15,7};
TreeNode root = demo.arrayToTree(arr, 0);
Boolean flag = demo.isBalanced(root);
System.out.println(flag);
}
}输出结果：
true543 二叉树的直径
题目描述
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
给定二叉树 [1,2,3,4,5] 1 / \ 2 3 / \ 4 5 返回 3
解题思路（深度优先搜索）
定义一个全局变量 res，用来记录最大直径。使用 dfs(node) 遍历所有的节点。
dfs(node) 的作用是：找出以 node 为根节点的二叉树的最大深度，将根节点的深度定义为 1。res 取值为以经过 root，左右子树的最大深度之和 leftDepth + rigthDepth。通过递归，找到 res 的最大值。
实现代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return res;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int leftDepth = dfs(node.left);
int rightDepth = dfs(node.right);
res = Math.max(res, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}
}复杂度分析
| 时间复杂度 | O(n)，其中 n 为二叉树的节点数 |
|---|---|
| 空间复杂度 | O(Height)，其中 Height为二叉树的高度 |
由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为 O(Height)O(Height)
在IntelliJ IDEA中测试
package com.cn.algorithm;
/**
* @Author: cyh
* @Description: 二叉树的直径
**/
public class DiameterOfBinaryTreeDemo {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
TreeNode arrayToTree(Integer[] array, int index) {
TreeNode root = null;
if (index < array.length) {
Integer value = array[index];
if (value == null) {
return null;
}
root = new TreeNode(value);
root.left = arrayToTree(array, 2*index + 1);
root.right = arrayToTree(array, 2*index + 2);
return root;
}
return root;
}
int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return res;
}
public int dfs(TreeNode node) {
if (node == null) return 0;
int leftDepth = dfs(node.left);
int rightDepth = dfs(node.right);
res = Math.max(res, leftDepth + rightDepth);
return Math.max(leftDepth, rightDepth) + 1;
}
public static void main(String[] args) {
DiameterOfBinaryTreeDemo demo = new DiameterOfBinaryTreeDemo();
Integer[] arr = {1,2,3,4,5};
TreeNode root = demo.arrayToTree(arr, 0);
int r = demo.diameterOfBinaryTree(root);
System.out.println(r);
}
}输出结果：
3226 翻转二叉树
题目描述
翻转一棵二叉树。
输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1
解法1 递归法（深度优先遍历）
交换左右节点，然后再递归的交换左节点，右节点。
实现代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
// 交换左右节点
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 递归
invertTree(root.left);
invertTree(root.right);
return root;
}
}复杂度分析
| 时间复杂度 | O(n)，其中 n 为二叉树的节点数 |
|---|---|
| 空间复杂度 | O(Height)，其中 Height为二叉树的高度 |
解法2 迭代法（广度优先遍历）
先将根节点放入到队列中，然后不断的迭代队列中的元素。对当前元素调换其左右子树的位置，然后：
- 判断其左子树是否为空，不为空就放入队列中
- 判断其右子树是否为空，不为空就放入队列中
代码实现
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
//每次都从队列中拿一个节点，并交换这个节点的左右子树
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
//如果当前节点的左子树不为空，则放入队列等待后续处理
if(tmp.left!=null) {
queue.add(tmp.left);
}
//如果当前节点的右子树不为空，则放入队列等待后续处理
if(tmp.right!=null) {
queue.add(tmp.right);
}
}
//返回处理完的根节点
return root;
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
在IntelliJ IDEA中测试
package com.cn.algorithm;
import java.util.*;
/**
* @Author: cyh
* @Description: 翻转二叉树
**/
public class InvertTreeDemo {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
TreeNode arrayToTree(Integer[] array, int index) {
TreeNode root = null;
if (index < array.length) {
Integer value = array[index];
if (value == null) {
return null;
}
root = new TreeNode(value);
root.left = arrayToTree(array, 2*index + 1);
root.right = arrayToTree(array, 2*index + 2);
return root;
}
return root;
}
List<Integer> treeToArray(TreeNode root, List<Integer> list) {
if (root == null) return null;
list.add(root.val);
if (root.left != null) {
list.add(root.left.val);
}
if (root.right != null) {
list.add(root.right.val);
}
treeToArray(root.left, list);
treeToArray(root.right, list);
return list;
}
/**
* 递归法（深度优先遍历）
* @param root
* @return
*/
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
// 交换左右节点
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 递归
invertTree(root.left);
invertTree(root.right);
return root;
}
/**
* 迭代法（广度优先遍历）
* @param root
* @return
*/
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
//将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
//每次都从队列中拿一个节点，并交换这个节点的左右子树
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
//如果当前节点的左子树不为空，则放入队列等待后续处理
if(tmp.left!=null) {
queue.add(tmp.left);
}
//如果当前节点的右子树不为空，则放入队列等待后续处理
if(tmp.right!=null) {
queue.add(tmp.right);
}
}
//返回处理完的根节点
return root;
}
public static void main(String[] args) {
InvertTreeDemo demo = new InvertTreeDemo();
Integer[] arr = {4,2,7,1,3,6,9};
TreeNode root = demo.arrayToTree(arr, 0);
TreeNode invertTree = demo.invertTree(root);
List<Integer> list = new ArrayList<>();
list = demo.treeToArray(invertTree, list);
System.out.println(list);
}
}输出结果：
[4, 7, 2, 7, 9, 6, 9, 6, 2, 3, 1, 3, 1]94 二叉树的中序遍历
题目描述
给定一个二叉树，返回它的中序遍历。
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]
解法1 递归法
使用经典的递归法实现，编写一个辅助函数实现递归。
实现代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
helper(root, list);
return list;
}
public void helper(TreeNode root, List<Integer> res) {
if (root.left != null) {
helper(root.left, res);
}
res.add(root.val);
if (root.right != null) {
helper(root.right, res);
}
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | 最坏情况下需要空间O(n)，平均情况为O(logn) |
解法2 迭代法
基于栈的遍历
代码实现
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while ( root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
解法3 颜色标记法
使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。
代码实现
class Solution {
public class ColorNode {
TreeNode root;
String color;
public ColorNode(TreeNode root, String color) {
this.root = root;
this.color = color;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<ColorNode> stack = new Stack<>();
if (root == null) return null;
stack.push(new ColorNode(root, "white"));
while (!stack.isEmpty() ) {
ColorNode colorNode = stack.pop();
if (colorNode.color.equals("white")) {
if (colorNode.root.right != null) {
stack.push(new ColorNode(colorNode.root.right, "white"));
}
stack.push(new ColorNode(colorNode.root, "gray"));
if (colorNode.root.left != null) {
stack.push(new ColorNode(colorNode.root.left, "white"));
}
} else {
res.add(colorNode.root.val);
}
}
return res;
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
在IntelliJ IDEA中测试
package com.cn.algorithm;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* @Author: cyh
* @Description: 二叉树的中序遍历
* 三种方法：1、递归法 2、迭代法 3、颜色标记法
**/
public class inorderTraversalDemo {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
/**
* 1.递归法
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
public void helper(TreeNode root, List<Integer> res) {
if (root != null) {
if (root.left != null) {
helper(root.left, res);
}
res.add(root.val);
if (root.right != null) {
helper(root.right, res);
}
}
}
/**
* 2.非递归版
* 用栈实现，迭代法
* @param root
* @return
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while ( root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
/**
* 3.颜色标记法
*/
public class ColorNode {
TreeNode root;
String color;
public ColorNode(TreeNode root, String color) {
this.root = root;
this.color = color;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<ColorNode> stack = new Stack<>();
if (root == null) return null;
stack.push(new ColorNode(root, "white"));
while (!stack.isEmpty() ) {
ColorNode colorNode = stack.pop();
if (colorNode.color.equals("white")) {
if (colorNode.root.right != null) {
stack.push(new ColorNode(colorNode.root.right, "white"));
}
stack.push(new ColorNode(colorNode.root, "gray"));
if (colorNode.root.left != null) {
stack.push(new ColorNode(colorNode.root.left, "white"));
}
} else {
res.add(colorNode.root.val);
}
}
return res;
}
/**
* 将数组转化为树结构
* @param array
* @param index
* @return
*/
TreeNode arrayToTree(Integer[] array, int index) {
TreeNode root = null;
if (index < array.length) {
Integer value = array[index];
if (value == null) {
return null;
}
root = new TreeNode(value);
root.left = arrayToTree(array, 2*index + 1);
root.right = arrayToTree(array, 2*index + 2);
return root;
}
return root;
}
public static void main(String[] args) {
Integer[] arr = {1,null,2,null,null,3};
inorderTraversalDemo it = new inorderTraversalDemo();
TreeNode root = it.arrayToTree(arr, 0);
List<Integer> list = it.inorderTraversal(root);
System.out.println(list);
}
}
输出结果：
[1, 3, 2]94 合并二叉树
题目描述
给定两个二叉树，你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7
解法1 递归法
前序遍历二叉树，再依次把访问到的节点值相加，题目没有说不能改变树的值和结构，我们不用再创建新的节点了，直接将树2合并到树1上再返回树就可以了。
实现代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null || t2 == null) {
return t1 == null ? t2 : t1;
}
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(h)，h为树的高度 |
解法2 迭代法
借助队列来实现广度优先遍历算法，只要两颗树的左节点都不为null，就把将他们放入队列中；同理只要两棵树的右节点都不为null了，也将他们放入队列中。然后我们不断的从队列中取出节点，把他们相加。
代码实现
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null || t2 == null) {
return t1 == null ? t2 : t1;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(t1);
queue.add(t2);
while (queue.size() > 0) {
TreeNode r1 = queue.remove();
TreeNode r2 = queue.remove();
r1.val += r2.val;
if (r1.left != null && r2.left != null) {
queue.add(r1.left);
queue.add(r2.left);
} else if (r1.left == null) {
r1.left = r2.left;
}
if (r1.right != null && r2.right != null) {
queue.add(r1.right);
queue.add(r2.right);
} else if (r1.right == null) {
r1.right = r2.right;
}
}
return t1;
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
在IntelliJ IDEA中测试
package com.cn.algorithm;
import java.util.LinkedList;
/**
* @Author: cyh
* @Description: 合并二叉树
**/
public class MergeTreesDemo {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
TreeNode arrayToTree(Integer[] array, int index) {
TreeNode root = null;
if (index < array.length) {
Integer value = array[index];
if (value == null) {
return null;
}
root = new TreeNode(value);
root.left = arrayToTree(array, 2*index + 1);
root.right = arrayToTree(array, 2*index + 2);
return root;
}
return root;
}
/**
* 递归法
* @param t1
* @param t2
* @return
*/
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null || t2 == null) {
return t1 == null ? t2 : t1;
}
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
/**
* 迭代法
* @param t1
* @param t2
* @return
*/
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1 == null || t2 == null) {
return t1 == null ? t2 : t1;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(t1);
queue.add(t2);
while (queue.size() > 0) {
TreeNode r1 = queue.remove();
TreeNode r2 = queue.remove();
r1.val += r2.val;
if (r1.left != null && r2.left != null) {
queue.add(r1.left);
queue.add(r2.left);
} else if (r1.left == null) {
r1.left = r2.left;
}
if (r1.right != null && r2.right != null) {
queue.add(r1.right);
queue.add(r2.right);
} else if (r1.right == null) {
r1.right = r2.right;
}
}
return t1;
}
public static void main(String[] args) {
MergeTreesDemo demo = new MergeTreesDemo();
Integer[] arr1 = {1, 3, 2, 5};
Integer[] arr2 = {2, 1, 3, null, 4, null, 7};
TreeNode root1 = demo.arrayToTree(arr1, 0);
TreeNode root2 = demo.arrayToTree(arr2, 0);
TreeNode root = demo.mergeTrees(root1, root2);
System.out.println(root); //方便断点调试
}
}112 路径总和
题目描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
给定如下二叉树，以及目标和 sum = 22 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
解法1 递归法
遍历整棵树，如果当前节点不是叶子，对它的所有孩子节点，递归调用 hasPathSum 函数，其中 sum 值减去当前节点的权值；如果当前节点是叶子，检查 sum 值是否为 0，也就是是否找到了给定的目标和。
实现代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
sum = sum - root.val;
if (root.left == null && root.right == null) {
return (sum == 0);
}
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | 最坏O(h)，最好O(log(n))，h为树的高度 |
解法2 迭代法
使用深度优先遍历进行迭代，通过辅助栈来实现。
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
LinkedList<TreeNode> stackTree = new LinkedList<>();
LinkedList<Integer> stackSum = new LinkedList<>();
if (root == null) return false;
stackTree.push(root);
stackSum.push(sum - root.val);
while (!stackTree.isEmpty()) {
TreeNode node = stackTree.pollLast();
Integer currSum = stackSum.pollLast();
if ((node.right == null) && (node.left == null) && (currSum == 0)) {
return true;
}
if (node.right != null) {
stackTree.add(node.right);
stackSum.add(currSum - node.right.val);
}
if (node.left != null) {
stackTree.add(node.left);
stackSum.add(currSum - node.left.val);
}
}
return false;
}
}复杂度分析
| 时间复杂度 | O(n) |
|---|---|
| 空间复杂度 | O(n) |
参考：
CyC：https://cyc2018.github.io/CS-Notes
