数据结构之二叉树

二叉树

本文的目的在于记录一些常用的二叉树问题解决手段。

二叉树的遍历

参考文档：
Binary Tree Postorder Traversal -- LeetCode
Binary Tree Inorder Traversal -- LeetCode
Binary Tree Preorder Traversal -- LeetCode

先序遍历
先序遍历
二叉树的先序遍历我们仍然介绍三种方法，第一种是递归，第二种是迭代方法，第三种是用线索二叉树。

递归是最简单的方法，算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。

public ArrayList<Integer> preorderTraversal(TreeNode root) {  
    ArrayList<Integer> res = new ArrayList<Integer>();  
    helper(root, res);  
    return res;  
}  
private void helper(TreeNode root, ArrayList<Integer> res)  
{  
    if(root == null)  
        return;  
    res.add(root.val);       /*中结点入list*/
    helper(root.left,res);   /*先左子树*/
    helper(root.right,res);  /*后右子树*/
}

接下来是迭代的做法，其实就是用一个栈来模拟递归的过程。所以算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)。

public ArrayList<Integer> preorderTraversal(TreeNode root)
{
    if(root == null) return res;  
    ArrayList<Integer> res = new ArrayList<Integer>();  
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();  
    while(root!=null || !stack.isEmpty())  
    {  
        if(root!=null)  
        {  
            stack.push(root);  
            res.add(root.val);  /*根加入list*/
            root = root.left;   /*找左子树，即使为空*/
        }  
        else  
        {  
            root = stack.pop();  /*如果当前结点为空，弹出一个结点（该结点的左子树为空），并找他的右子树*/
            root = root.right;  
        }  
    }  
    return res;  
}

最后我们介绍一种比较复杂的方法，就是如何用常量空间来遍历一颗二叉树。这种方法叫Morris Traversal。想用O(1)空间进行遍历，因为不能用栈作为辅助空间来保存付节点的信息，重点在于当访问到子节点的时候如何重新回到父节点（当然这里是指没有父节点指针，如果有其实就比较好办，一直找遍历的后驱结点即可）。Morris遍历方法用了线索二叉树，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。

算法具体分情况如下：
2.1 如果当前结点的左孩子为空，则输出当前结点并将其当前节点赋值为右孩子。
2.2 如果当前节点的左孩子不为空，则寻找当前节点在中序遍历下的前驱节点（也就是当前结点左子树的最右孩子）。接下来分两种情况：
2.2.1 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点（做线索使得稍后可以重新返回父结点）。然后将当前节点更新为当前节点的左孩子。
2.2.2 如果前驱节点的右孩子为当前节点，表明左子树已经访问完，可以访问当前节点。将前驱结点的右孩子重新设为空（恢复树的结构）。输出当前节点。当前节点更新为当前节点的右孩子。

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    TreeNode cur = root;
    TreeNode pre = null;
    while(cur!=null)
    {
        /*如果当前结点的左子树为空，则输出当前结点，并将当前结点赋值为右子树*/
        if (cur.left == null)
        {
            res.add(cur.val);
            cur = cur.right;
        }
        /*如果当前结点的左子树不为空，则寻找当前结点在“中序遍历”下的前驱结点，也就是当前结点的左子树的最右叶子*/
        else
        {
            pre = cur.left; /*当前结点的左子树*/

            /*左子树的最右叶子,保证不为空，且未遍历过*/
            while(pre.right!=null && pre.right != cur)
                pre = pre.right;

            /*如果前驱节点的右孩子为空，将前驱结点的右孩子设置为当前节点（做线索使得稍后可以重新返回父结点）。  
              然后将当前节点更新为当前节点的左孩子。*/  
            if(pre.right == null)
            {
                pre.right = cur;
                res.add(cur.val);
                cur = pre.left;
            }
            /*如果前驱节点的右孩子为当前节点，表明左子树已经访问完，可以访问当前节点。将它的右孩子重新设为空（恢复树的结构）。  
              输出当前节点。当前节点更新为当前节点的右孩子。*/  
            else
            {
                pre.right = null;
                cur = cur.right;
            }
        }
    }
    return res;
}

中序遍历
中序遍历
通常，实现二叉树的遍历有两个常用的方法：一是用递归，二是使用栈实现的迭代方法。下面分别介绍。

递归应该最常用的算法，算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。

public ArrayList<Integer> inorderTraversal(TreeNode root) {  
    ArrayList<Integer> res = new ArrayList<Integer>();  
    helper(root, res);  
    return res;  
}  
private void helper(TreeNode root, ArrayList<Integer> res)  
{  
    if(root == null)  
        return;  
    helper(root.left,res);   /*先左子树*/
    res.add(root.val);       /*中结点入list*/
    helper(root.right,res);  /*后右子树*/
}

栈实现迭代，其实就是用一个栈来模拟递归的过程。所以算法时间复杂度也是O(n)，空间复杂度是栈的大小O(logn)。
过程中维护一个node表示当前走到的结点（不是中序遍历的那个结点），实现的代码如下：

public ArrayList<Integer> inorderTraversal(TreeNode root)
{  
    ArrayList<Integer> res = new ArrayList<Integer>();  
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();  

    while(root!=null || !stack.isEmpty())  
    {  
        /*找到最左边的子结点*/
        if(root!=null)  
        {  
            stack.push(root);  
            root = root.left;  
        }  
        else  
        {  
            root = stack.pop();  
            res.add(root.val);  
            root = root.right;  
        }  
    }  
    return res;  
}

最后我们介绍一种比较复杂的方法，就是如何用常量空间来中序遍历一颗二叉树。这种方法叫Morris Traversal。想用O(1)空间进行遍历，因为不能用栈作为辅助空间来保存付节点的信息，重点在于当访问到子节点的时候如何重新回到父节点（当然这里是指没有父节点指针，如果有其实就比较好办，一直找遍历的后驱结点即可）。Morris遍历方法用了线索二叉树，这个方法不需要为每个节点额外分配指针指向其前驱和后继结点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。

算法具体分情况如下：
2.1 如果当前结点的左孩子为空，则输出当前结点,并将其当前节点赋值为右孩子。
2.2 如果当前节点的左孩子不为空，则寻找当前节点在中序遍历下的前驱节点（也就是当前结点左子树的最右孩子）。接下来分两种情况：
2.2.1 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点（做线索使得稍后可以重新返回父结点）。然后将当前节点更新为当前节点的左孩子。
2.2.2 如果前驱节点的右孩子为当前节点，表明左子树已经访问完，可以访问当前节点。将前驱结点的右孩子重新设为空（恢复树的结构）。输出当前节点。当前节点更新为当前节点的右孩子。

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    TreeNode cur = root;
    TreeNode pre = null;
    while(cur!=null)
    {
        /*如果当前结点的左子树为空，则输出当前结点，并将当前结点赋值为右子树*/
        if (cur.left == null)
        {
            res.add(cur.val);
            cur = cur.right;
        }
        /*如果当前结点的左子树不为空，则寻找当前结点在“中序遍历”下的前驱结点，也就是当前结点的左子树的最右叶子*/
        else
        {
            pre = cur.left; /*当前结点的左子树*/
            /*左子树的最右叶子,保证不为空，且未遍历过*/
            while(pre.right!=null && pre.right != cur)
                pre = pre.right;
            /*如果前驱节点的右孩子为空，将前驱结点的右孩子设置为当前节点（做线索使得稍后可以重新返回父结点）。  
              然后将当前节点更新为当前节点的左孩子。*/  
            if(pre.right == null)
            {
                pre.right = cur;
                cur = pre.left;
            }
            /*如果前驱节点的右孩子为当前节点，表明左子树已经访问完，可以访问当前节点。将它的右孩子重新设为空（恢复树的结构）。  
              输出当前节点。当前节点更新为当前节点的右孩子。*/  
            else
            {
                pre.right = null;
                res.add(cur.val);
                cur = cur.right;
            }
        }
    }
    return res;
}

后序遍历

后序遍历我们还是介绍三种方法，第一种是递归，第二种是迭代方法，第三种是用线索二叉树。
递归算法的时间复杂度是O(n), 而空间复杂度则是递归栈的大小，即O(logn)。

public ArrayList<Integer> postorderTraversal(TreeNode root) {  
    ArrayList<Integer> res = new ArrayList<Integer>();  
    helper(root, res);  
    return res;  
}  
private void helper(TreeNode root, ArrayList<Integer> res)  
{  
    if(root == null)  
        return;  
    helper(root.left,res);   /*左子树递归*/
    helper(root.right,res);  /*右子树递归*/
    res.add(root.val);       /*根节点加入*/
}

后来再看wiki的时候发现有跟中序遍历和先序遍历非常类似的解法，容易统一进行记忆，思路可以参考其他两种，区别是最下面在弹栈的时候需要分情况一下：

如果当前栈顶元素的右结点存在并且还没访问过（也就是右结点不等于上一个访问结点），那么就把当前结点移到右结点继续循环；
如果栈顶元素的右子树是空或者已经访问过，那么说明栈顶元素的左右子树都访问完毕，应该访问自己继续回溯了。

public List<Integer> postorderTraversal(TreeNode root) {  
    List<Integer> res = new ArrayList<Integer>();  
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();  
    if(root == null)  
    {  
        return res;  
    }  
    TreeNode pre = null;  /*记录右结点是否访问过*/
    while(root != null || !stack.isEmpty())  
    {  
        if(root!=null)  
        {  
            stack.push(root);  
            root = root.left;  /*找到最左边的树结点*/
        }  
        else  
        {  
            TreeNode peekNode = stack.peek();  /*栈顶元素*/
            if(peekNode.right != null && pre != peekNode.right)  
            {  
                root = peekNode.right;  
            }  
            else  
            {  
                stack.pop();  
                res.add(peekNode.val);  
                pre = peekNode;  
            }  
        }  
    }  
    return res;  
}

层级遍历

用队列来维护.算法的复杂度是就结点的数量:O(n)，空间复杂度是一层的结点数:O(n)。

vector<int> PrintFromTopToBottom(TreeNode* root)
{
    vector<int> vRet;
    queue<TreeNode*> queTree;

    if(root == nullptr) return vRet;
    queTree.push(root);

    while(!queTree.empty())
    {
        /*队列先进先出，进入vector*/
        TreeNode *tmp = queTree.front();
        vRet.push_back(tmp->val);
        /*左右子树入队列*/
        if(tmp->left != nullptr) {
            queTree.push(tmp->left);
        }
        if(tmp->right != nullptr) {
            queTree.push(tmp->right);
        }
        /*出队*/
        queTree.pop();
    }
    return vRet;
}

二叉树的操作

二叉树镜像
操作给定的二叉树，将其变换为源二叉树的镜像。也就是左子树转右子树。

void Mirror(TreeNode *pRoot) {
    if(pRoot == nullptr) return;

    //swap
    TreeNode *tmp = pRoot->left;
    pRoot->left = pRoot->right;
    pRoot->right = tmp;

    //递归左右
    Mirror(pRoot->left);
    Mirror(pRoot->right);
}

二叉树深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
```
int TreeDepth(TreeNode* pRoot)
{
    if(pRoot==nullptr) return 0;
    return max(1+TreeDepth(pRoot->left),1+TreeDepth(pRoot->right));
}
```

对称树判断

是否对称树

boolean isSymmetrical(TreeNode pRoot)
{
    return judge(pRoot,pRoot);
}

public boolean judge(TreeNode pRoot,TreeNode root){
    if(pRoot== null && root == null){
        return true;
    }
    if(pRoot==null || root == null){
        return false;
    }
    if(pRoot.val != root.val)
        return false;
    return judge(pRoot.left,root.right) && judge(pRoot.right,root.left);
}

平衡树的判断

输入一颗二叉树判断是否为平衡树

方法一：

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null)
            return true;
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        if (Math.abs(left-right) <= 1)
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        else
            return false;
    }

    private int TreeDepth(TreeNode root) {
        if (root == null)
            return 0;
        int left = TreeDepth(root.left)+1;
        int right = TreeDepth(root.right)+1;
        return Math.max((1 + TreeDepth(root.left)), (1 + TreeDepth(root.right)));
    }
}

方法二：-1代表不平衡，有个子树不平衡那么整个树肯定不平衡

class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        return getDepth(pRoot) != -1;
    }
    int getDepth(TreeNode* pRoot)
    {
        if (pRoot == nullptr) return 0;
        int left = getDepth(pRoot->left);
        if (left == -1) return -1;
        int right = getDepth(pRoot->right);
        if (right == -1) return -1;
        return abs(left - right) > 1 ? -1 : 1 + max(left, right);
    }
};

二叉树转链表

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

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootofTree)
    {
        if(pRootofTree == nullptr) return nullptr;
        TreeNode* pre = nullptr;
        helper(pRootofTree,pre);

        TreeNode* result = pRootofTree;

        while(result->left)
        {
            result = result->left;
        }
        return result;
    }
    void helper(TreeNode* pRootofTree,TreeNode*& pre)
    {
        if(pRootofTree == nullptr) return;
        helper(pRootofTree->left, pre);

        pRootofTree->left = pre;

        if(pre) pre->right = pRootofTree;

        pre = pRootofTree;

        helper(pRootofTree->right, pre);
    }
};

BST中第K大的数

查找二叉平衡树中第 K 大的元素

Binary Search Tree是有序的，先找最右，当数字小于K的时候，再逐步找左子树。
时间复杂度：O(h + k). The code first traverses down to the rightmost node which takes O(h) time, then traverses k elements in O(k) time.

// A function to find k'th largest element in a given tree.
void kthLargestUtil(Node *root, int k, int &c)
{
    // Base cases, the second condition is important to
    // avoid unnecessary recursive calls
    if (root == NULL || c >= k)
        return;

    // Follow reverse inorder traversal so that the
    // largest element is visited first
    kthLargestUtil(root->right, k, c);

    // Increment count of visited nodes 
    c++;

    // If c becomes k now, then this is the k'th largest  
    if (c == k)
    {
        cout << "K'th largest element is "
            << root->key << endl;
        return;
    }

    // Recur for left subtree
    kthLargestUtil(root->left, k, c);
}

// Function to find k'th largest element
void kthLargest(Node *root, int k)
{
    // Initialize count of nodes visited as 0
    int c = 0;

    // Note that c is passed by reference
    kthLargestUtil(root, k, c);
}

打印和根节点距离为K的结点

查找树中与根节点距离为 k 的节点

空间复杂度： O(n) where n is number of nodes in the given binary tree.

void printKDistant(node *root , int k)  
{  
    if(root == NULL)  
        return;  
    if( k == 0 )  
    {  
        cout << root->data << " ";  
        return ;  
    }  
    else
    {  
        printKDistant( root->left, k - 1 ) ;  
        printKDistant( root->right, k - 1 ) ;  
    }  
}

打印所有祖先节点

查找二叉树中某个节点所有祖先节点

时间复杂度：Time Complexity: O(n) . where n is the number of nodes in the given Binary Tree

/* If target is present in tree, then prints the ancestors
and returns true, otherwise returns false. */
bool printAncestors(struct node *root, int target)
{
    /* base cases */
    if (root == NULL)
        return false;

    if (root->data == target)
        return true;

    /* If target is present in either left or right subtree of this node,
        then print this node */
    if ( printAncestors(root->left, target) ||
        printAncestors(root->right, target) )
    {
        cout << root->data << " ";
        return true;
    }

    /* Else return false */
    return false;
}

是否是Binary Search Tree

每当遍历到一个新节点时和其上一个节点比较，如果不大于上一个节点那么则返回false，全部遍历完成后返回true

bool isValidBST(TreeNode* root) {
    TreeNode *tmpNode = NULL;
    return helper(root, tmpNode);
}
bool helper(TreeNode* root, TreeNode* &tmpNode)
{
    /*中序遍历，只比较判断，不进行其他处理*/
    if (root == NULL)
    {
        return true;
    }
    bool left = helper(root->left, tmpNode);
    if (tmpNode != NULL && tmpNode->val >= root->val)
    {
        return false;
    }
    tmpNode = root;
    return left && helper(root->right, tmpNode);
}

路径求和

bool hasPathSum(TreeNode* root, int sum) {
    if (NULL == root) return false;
    if (root->left==NULL && root->right==NULL && root->val==sum) return true;
    return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
}

问题变化：记录路径结点。

vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>> ret;
    if(root==NULL) return ret;
    vector<int>item;
    helper(root, sum, item, ret);  
    return ret;
}
void helper(TreeNode* root, int sum, vector<int>& item, vector<vector<int>>& ret)
{
    if(root==NULL) return;
    item.push_back(root->val);
    if(root->right==NULL&&root->left==NULL&& sum ==root->val)
    {
        ret.push_back(item);
    }
    helper(root->left, sum-root->val, item, ret);
    helper(root->right, sum-root->val, item, ret);

    //作为静态变量存储需要恢复现场
    item.pop_back();//很关键
}