常见二叉树解题集合

二叉树思维篇：填充节点的右侧指针、二叉树展开为链表、树的子结构

116.填充节点的右侧指针

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if(root==NULL) return NULL;
        traverse(root->left, root->right);
        return root;
    }
    void traverse(Node* node1, Node* node2){
        if(node1==NULL || node2==NULL){
            return ;
        }
        //前序遍历位置
        //将传入的两个节点连起来
        node1->next=node2;

        //连接相同父节点的两个字节点
        traverse(node1->left, node1->right);
        traverse(node2->left, node2->right);
        //连接跨越父节点的两个子节点
        traverse(node1->right, node2->left);
    }
};

/*
// Definition for a Node.
type Node struct {
    Val int
    Left *Node
    Right *Node
    Next *Node
}
*/
func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    traverse(root.Left, root.Right)
    return root
}

func traverse(node1, node2 *Node) {
    if node1 == nil || node2 == nil {
        return
    }
    //前序遍历位置
    //将传入的两个节点连起来
    node1.Next = node2

    //连接相同父节点的两个字节点
    traverse(node1.Left, node1.Right)
    traverse(node2.Left, node2.Right)
    //连接跨越父节点的两个子节点
    traverse(node1.Right, node2.Left)
}

114.二叉树展开为链表

class Solution {
public:
    void flatten(TreeNode* root) {
        //递归实现，先将root的左右子树开展成单链表，再将右子树接到左子树
        //然后将整个左子树作为原树的右子树

        //base case
        if(root == nullptr) return ;
        
        //将左右子树拉平
        flatten(root->left);
        flatten(root->right);

        /***后序遍历位置***/
        //用两个临时节点来存左右子树
        TreeNode* left = root->left;
        TreeNode* right = root->right;

        //将左子树接过去
        root->left = nullptr;
        root->right = left;

        TreeNode* p = root;
        while(p->right){
            p = p->right;
        }
        p->right = right;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func flatten(root *TreeNode) {
    //递归实现，先将root的左右子树开展成单链表，再将右子树接到左子树
    //然后将整个左子树作为原树的右子树

    //base case
    if root == nil {
        return
    }
    
    //将左右子树拉平
    flatten(root.Left)
    flatten(root.Right)

    /***后序遍历位置***/
    //用两个临时节点来存左右子树
    left := root.Left
    right := root.Right

    //将左子树接过去
    root.Left = nil
    root.Right = left

    p := root
    for p.Right != nil {
        p = p.Right
    }
    p.Right = right
}

offer I 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

思路：

定义两个指针pre和head，pre指针用于保存中序遍历的前一个节点，head指针用于记录排序链表的头节点。

中序遍历二叉树，遍历顺序就是双线链表的建立顺序。只需要在中序遍历的过程中，修改每个节点的左右指针，将零散的节点连接成双向循环链表。

/* // Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node() {}
    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }
    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};*/
class Solution {
public:
    Node* pre=NULL; //用于保存中序遍历的前一个节点
    Node* head=NULL; //用于记录排序链表的头节点
    Node* treeToDoublyList(Node* root) {
        if(root==NULL) return root;
        dfs(root);
        
        //连接首尾
        head->left = pre;
        pre->right = head;
        
        return head;
    }
    void dfs(Node* root){
        //base case
        if(root==NULL) return;
        //左子树
        dfs(root->left);

        /*中序遍历位置*/
        if(pre!=NULL) pre->right = root; //将前驱节点的右指针指向当前根节点
        else head = root; //保存链表头节点
        root->left = pre; //root的left指针指向其前驱
        pre = root; //前驱节点右移
        
        //右子树
        dfs(root->right);
    }
};

/* // Definition for a Node.
type Node struct {
    Val int
    Left *Node
    Right *Node
}
*/
type Solution struct {
    pre *Node  //用于保存中序遍历的前一个节点
    head *Node //用于记录排序链表的头节点
}

func treeToDoublyList(root *Node) *Node {
    if root == nil {
        return root
    }
    s := &Solution{}
    s.dfs(root)
    
    //连接首尾
    s.head.Left = s.pre
    s.pre.Right = s.head
    
    return s.head
}

func (s *Solution) dfs(root *Node) {
    //base case
    if root == nil {
        return
    }
    //左子树
    s.dfs(root.Left)

    /*中序遍历位置*/
    if s.pre != nil {
        s.pre.Right = root //将前驱节点的右指针指向当前根节点
    } else {
        s.head = root //保存链表头节点
    }
    root.Left = s.pre //root的left指针指向其前驱
    s.pre = root //前驱节点右移
    
    //右子树
    s.dfs(root.Right)
}

offer 26.树的子结构

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        //先序遍历树 A 中的每个节点 n_A ; (对应函数 isSubStructure(A, B) )
        //判断树 A 中 以 n_A 为根节点的子树是否包含树 B ; (对应函数 helper(A, B) )

        if(A==NULL || B==NULL) return false;
        return helper(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
    bool helper(TreeNode* A, TreeNode* B){
        if(B==NULL) return true;
        if(A==NULL) return false;
        if(A->val!=B->val) return false;
        return helper(A->left, B->left) && helper(A->right, B->right);
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    //先序遍历树 A 中的每个节点 n_A ; (对应函数 isSubStructure(A, B) )
    //判断树 A 中 以 n_A 为根节点的子树是否包含树 B ; (对应函数 helper(A, B) )

    if A == nil || B == nil {
        return false
    }
    return helper(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func helper(A *TreeNode, B *TreeNode) bool {
    if B == nil {
        return true
    }
    if A == nil {
        return false
    }
    if A.Val != B.Val {
        return false
    }
    return helper(A.Left, B.Left) && helper(A.Right, B.Right)
}

572.另一棵树的子树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(root==nullptr) return false;

        return isSame(root, subRoot) || isSubtree(root->left, subRoot) 
               || isSubtree(root->right, subRoot);
    }
    bool isSame(TreeNode* a, TreeNode* b){
        if(a==nullptr && b==nullptr) return true;
        if(a==nullptr || b==nullptr) return false;
        if(a->val!=b->val) return false;

        return isSame(a->left, b->left) && isSame(a->right, b->right);
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return false
    }

    return isSame(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}

func isSame(a *TreeNode, b *TreeNode) bool {
    if a == nil && b == nil {
        return true
    }
    if a == nil || b == nil {
        return false
    }
    if a.Val != b.Val {
        return false
    }

    return isSame(a.Left, b.Left) && isSame(a.Right, b.Right)
}

236.二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //后序遍历
        
        //base case
        if(root==NULL) return NULL;
        if(root==p || root==q) return root;

        TreeNode* left=lowestCommonAncestor(root->left, p, q);
        TreeNode* right=lowestCommonAncestor(root->right, p, q);

        if(left!=NULL && right!=NULL) return root;

        if(left==NULL && right==NULL) return NULL;

        return left==NULL ? right : left;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    //后序遍历
    
    //base case
    if root == nil {
        return nil
    }
    if root == p || root == q {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left != nil && right != nil {
        return root
    }

    if left == nil && right == nil {
        return nil
    }

    if left == nil {
        return right
    }
    return left
}

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // 后序遍历
        
        //base case
        if(root==nullptr) return 0;
        if(root->val==o1 || root->val==o2) return root->val;
        
        int val1 = lowestCommonAncestor(root->left, o1, o2);
        int val2 = lowestCommonAncestor(root->right, o1, o2);
        
        if(val1!=0 && val2!=0) return root->val;
        
        if(val1==0 && val2==0) return 0;
        
        return val1==0 ? val2 : val1;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
    // 后序遍历
    
    //base case
    if root == nil {
        return 0
    }
    if root.Val == o1 || root.Val == o2 {
        return root.Val
    }
    
    val1 := lowestCommonAncestor(root.Left, o1, o2)
    val2 := lowestCommonAncestor(root.Right, o1, o2)
    
    if val1 != 0 && val2 != 0 {
        return root.Val
    }
    
    if val1 == 0 && val2 == 0 {
        return 0
    }
    
    if val1 == 0 {
        return val2
    }
    return val1
}

判断是不是完全二叉树

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        // write code here
        //空树一定是完全二叉树
        if(root==nullptr) return true;
        queue<TreeNode*> q;
        q.push(root);
        //定义一个首次出现的标记位
        bool flag = false;
        
        while(!q.empty()){
            int n=q.size();
            for(int i=0;i<n;i++){
                TreeNode* cur = q.front();
                q.pop();
                //标记第一次遇到空节点
                if(cur==nullptr){
                    flag = true;
                }else{
                    //后续访问已经遇到空节点了，说明经过了叶子
                    if(flag) return false;
                    q.push(cur->left);
                    q.push(cur->right);
                }
            }
        }
        return true;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCompleteTree(root *TreeNode) bool {
    // write code here
    //空树一定是完全二叉树
    if root == nil {
        return true
    }
    queue := []*TreeNode{root}
    //定义一个首次出现的标记位
    flag := false
    
    for len(queue) > 0 {
        n := len(queue)
        for i := 0; i < n; i++ {
            cur := queue[0]
            queue = queue[1:]
            //标记第一次遇到空节点
            if cur == nil {
                flag = true
            } else {
                //后续访问已经遇到空节点了，说明经过了叶子
                if flag {
                    return false
                }
                queue = append(queue, cur.Left)
                queue = append(queue, cur.Right)
            }
        }
    }
    return true
}

958. 二叉树的完全性检验

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        //广度优先遍历

        //空树一定是完全二叉树
        if(root==nullptr) return true;
        queue<TreeNode*> q;
        q.push(root);
        //定义一个首次出现的标记位
        bool flag = false;

        while(!q.empty()){
            int n=q.size();
            for(int i=0;i<n;i++){
                TreeNode* cur = q.front();
                q.pop();
                //标记第一次遇到空节点
                if(cur==nullptr){
                    flag=true;
                }else{
                    //后续节点遇到空节点了，说明经过了叶子节点
                    if(flag) return false;
                    q.push(cur->left);
                    q.push(cur->right);
                }
            }
        }
        return true;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCompleteTree(root *TreeNode) bool {
    //广度优先遍历

    //空树一定是完全二叉树
    if root == nil {
        return true
    }
    queue := []*TreeNode{root}
    //定义一个首次出现的标记位
    flag := false

    for len(queue) > 0 {
        n := len(queue)
        for i := 0; i < n; i++ {
            cur := queue[0]
            queue = queue[1:]
            //标记第一次遇到空节点
            if cur == nil {
                flag = true
            } else {
                //后续节点遇到空节点了，说明经过了叶子节点
                if flag {
                    return false
                }
                queue = append(queue, cur.Left)
                queue = append(queue, cur.Right)
            }
        }
    }
    return true
}

判断是不是平衡二叉树

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot==nullptr) return true;
        if(abs(maxDepth(pRoot->left)-maxDepth(pRoot->right))>1) return false;
        return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
    }
    int maxDepth(TreeNode* root){
        if(root==nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func IsBalanced_Solution(pRoot *TreeNode) bool {
    if pRoot == nil {
        return true
    }
    if abs(maxDepth(pRoot.Left) - maxDepth(pRoot.Right)) > 1 {
        return false
    }
    return IsBalanced_Solution(pRoot.Left) && IsBalanced_Solution(pRoot.Right)
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

863. 二叉树中所有距离为 K 的结点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

// 思路： unordered_map + dfs
class Solution {
public:
    vector<int> res;
    unordered_map<int, TreeNode*> mp;
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        //从根节点出发，dfs，记录每个节点的父节点
        findParent(root);

        //从target出发，寻找深度为k的节点
        dfs(target, NULL, 0, k);
        return res;
    }

    void findParent(TreeNode* root){
        if(root->left!=NULL){
            mp[root->left->val]=root;
            findParent(root->left);
        }
        if(root->right!=NULL){
            mp[root->right->val]=root;
            findParent(root->right);
        }
    }

    void dfs(TreeNode* root, TreeNode* parent, int depth, int k){
        if(root==NULL){
            return;
        }
        if(depth==k){
            res.push_back(root->val);
            return;
        }
        if(root->left!=parent){
            dfs(root->left, root, depth+1, k);
        }
        if(root->right!=parent){
            dfs(root->right, root, depth+1, k);
        }
        if(mp[root->val]!=parent){
            dfs(mp[root->val], root, depth+1, k);
        }
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 思路： map + dfs
func distanceK(root *TreeNode, target *TreeNode, k int) []int {
    res := []int{}
    mp := make(map[int]*TreeNode)
    
    //从根节点出发，dfs，记录每个节点的父节点
    var findParent func(*TreeNode)
    findParent = func(node *TreeNode) {
        if node.Left != nil {
            mp[node.Left.Val] = node
            findParent(node.Left)
        }
        if node.Right != nil {
            mp[node.Right.Val] = node
            findParent(node.Right)
        }
    }
    findParent(root)

    //从target出发，寻找深度为k的节点
    var dfs func(*TreeNode, *TreeNode, int, int)
    dfs = func(node *TreeNode, parent *TreeNode, depth int, k int) {
        if node == nil {
            return
        }
        if depth == k {
            res = append(res, node.Val)
            return
        }
        if node.Left != parent {
            dfs(node.Left, node, depth+1, k)
        }
        if node.Right != parent {
            dfs(node.Right, node, depth+1, k)
        }
        if mp[node.Val] != parent {
            dfs(mp[node.Val], node, depth+1, k)
        }
    }
    dfs(target, nil, 0, k)
    
    return res
}